Ok... three options.
1 - Are you running froyo 2.2? If so use the move apps 2 sd card feature to free up some valuable space. If not, skip to step 2. Or I can talk you through how to update to 2.2
2 - There is a process which is in my signature (the last one) which is a process that allows you move all apps as opposed to just the ones the developers / market allows. It is very safe, quick, easy and doesn't require rooting.
3 - Are you rooted? If so read on, if not do so. Then once rooted, you can flash a rom with a2sd which allows you to store much more data than number 1 (like some cache) etc and will free up lots of space.
Ask for more info, see my sig or user Danfrance has some particularly useful and good FAQ's on this subject.