I think, there is something buggy with the current gallery/phpthumb - combination (frontend and backend)
Has anyone any idea how I could fix this one? Or should I try some another gallery plugin?
Think this problem was related to folder permissions. I Believe it was fixed in Gallery 1.6.2-pl. If you haven't already, upgrade to latest version and let us know if you still have this issue.
Check your /public_html/config.core.php file. Make sure you are pointing to the correct folder. That worked for me.