My issue solved by hosting provider. Not sure what they did though - think permissions on the gallery. Have tested this further on a 2nd hosting service (Bluehost) and it worked fine.
Apparently one known bug/limitation (perhaps relevant to some posts in this thread) - flash upload does not work for a user who is not an administrator, workaround is to use the zip file upload.
iwassertein, I am hosting through blue host and have the same problem even though I am an admisnistrator I can't upload, do you know what they changed so flash uploader would work?