Right recently I've noticed some updates for packages I have installed complaining about missing packages or being of an old version. At first I thought it was just an issue with a package in devel and wrote it off as "that's what you get using devel packages", but now I'm seeing it in other packages.

Missing packages in question are:
librtcom-eventlogger1 >= 1.3-4+0m5
hildon-home >=0.3.66-2+0m5
libqt4-core >=4.6.2~git20100224
libqt4-dbus >=4.6.2~git20100224
libqt4-gui >=4.6.2~git20100224
libqt4-network >=4.6.2~git20100224
libqt4-xml >=4.6.2~git20100224

And today I went to Ovi store and it told me I needed to upgrade Maemo, but I've got no upgrade in application manager to apply. Just the updates to applications complaining about missing packages.

What version firmware are you running?

Go to "Settings" -> "About product" to find out.

You're looking for:

Nokia N900
Maemo 5
Version 10.2010.19-1.xxx.1

Not sure of your geographical location, but the 10.2010 indicates the latest version. If it's different then you more than likely need to update the firmware.

I've got:

Nokia N900
Maemo 5
Version 3.2010.02-8.203.1

How do I update then? The last update I did came through application manager some months back.

You're on the generic UK firmware, so you should have been notified about the update. If not, you've probably done something which has removed the mp-fremantle-203-pr package. The simplest option is to reflash with the latest firmware. Your other option is to do "apt-get install mp-fremantle-203-pr" as root in X Terminal - this will pull in the whole PR1.2 update though, so you'll probably also need to tell apt-get to store the temporary files elsewhere (otherwise you'll run out of rootfs space). Unfortunately I can't recall the command-line option you need for that, but a search of the apt-get manual page should tell you.

I get told that mp-fremantle-203-pr is already the newest version.