Finally got the gallery working again. Tried many other gallery plugins in the past, but they all either didn’t work or just sucked due to lack of FTP upload capability.
I have to admit that I kinda given up, until I saw that there was a new upgrade to Lazyest Gallery (the old gallery plugin that died when I upgraded WP to 2.5). So I tried, and it worked!
Seems the real author had disappeared and that some guy took up the torch. Thanks a lot man. He just earned a 15 € donation from yours truly.
So hopefully there will be some updates in the gallery shortly.
If you are interested in the Lazyest Gallery plugin, look here.