Cais- I got the same problem.
I changed the Permalinks as suggested but no joy. For the PHP memory limit, mine is a virgin site from InMotion.
The software appears to go through the motions of uploading. I can create albums and galleries and when I check into raw files /directories, I don’t see any pictures getting added.
I see other people on the forum commenting about a similar problem after they updated wordpress to current edition. I’m new to WP so don’t know how long that revision has been released, and how many people have installed NextGEN since.