I stumbled across a cure for my N73 memory low and update gallery problem.
It turns out that the memory problem is caused by the phone memory copying image files etc even though they've been deleted from the memory card. This fills the phone memory although you can't access the files in order to delete them. Because I updated my phone's firmware yesterday, I instantly suffered the same problem as others have experienced - the gallery did not find any images/video etc.
The 'cure' was to enable the 'Active Standby' facility. That's the bit that puts icons on your desktop. When you click on the gallery from the desktop icon, the phone searches for appropriate files and fills up its library.
On my phone, it found all of the cached/copied photos etc that I had deleted some time ago from my memory disk. I simply 'marked' them all and deleted them.
I FREED UP ALMOST 40MEG OF PHONE MEMORY!!!
I have thus solved two problems in one.
I have since disabled the active desktop, and the gallery has continued to work as normal from my usual shortcut key.
I'm not going to claim that this will definitley cure everyone's problems, but it did for me and I wish you all good luck.
Cheers
Pheeel