I have the same problem (I'm an app hog!).
On my phone, which is not rooted, I can move some, not all apps to the SD card.
I can do it with Home>Menu>Applications>Manage Applications <click on app to move>, choose Move to SDcard.
Easier to use Android Assistant's Tools menu with SDcard mover.
My phone seems very inconsistent about when (at what storage level) it complains. But then, it's inconsistent about a lot of things...