I have exactly the same problem. I can create an image gallery on any page using the gallery tags, but new images do not appear in the Special:Newimages pages. I have tried uploading new images but although they are listed in the Image List page, they don't appear in the New Images gallery page.
Mediawiki 1.4
Mysql 4.0.24 - standard-log
Php 4.3.10 (cgi)
Ken Ross