[Plugin: VideoGall] Fatal error: Allowed memory size

This is not a plugin-specific issue. Try increasing the memory available to PHP.

Done,
Increased WordPress and PHP memory to 96M and doesn’t help. Removing the plugin, reverting memory changes and downgraded to version 2.2 and everything worked again. So this IS an plugin-specific issue

Sorry but it isn’t. Did you try step 4?

Yes I did it and it didn’t help at all

I had the very same problem.
The problem was this line in videogall.php:

ini_set("memory_limit","50M");

It was putting a cap on global WP available memory.

I found out using a memory usage plugin (WP-Memory-Usage). Every time I activated Videogall the memory limit would jump from 128M (as defined in php.ini) to 50M.
Editing this line solved the problem.