OK chaps I also could not update over the air and Nokia software updater kept saying that I had the latest firmware.

What I did was to create a backup and delete some apps and try after each deletion. The app that stop me from updating was Tux Race 0.4.

So after deleting loads this was the naughty app. Before deleting, rootsf was over 50 mb free and that was before getting rid of Tux Race.

Hope this helps....