What update manager where you using? Yum or Up2date?
If you were using up2date though then I can't help you, sorry. Never used it with Fedora (as a matter of fact I removed it) and back in the day with Red hat 9 I didn't need to delete anything.
Before you start there's something you might want to do first:
Somewhere in the panel menu (System Settings) there should be something called Add/Remove Applications. Go through the list and remove everything you definitely won't need. This way you can free up pretty much disk space.
If you did that, try updating the stuff again. If it doesn't work and you're using Yum (not up2date), open a terminal and type
(The "$" is the prompt itself, don't type it in. It shows that you're working with a user account)
You'll get asked for your root password. When you type it in there won't be any ***s so don't be surprised.
So either you want to delete a couple of files, or you want to remove everything and start over. If you want to do the latter, execute the following command in the terminal
(Again, # is the prompt and shows that you're currently working as root).
This should delete all stored packages, headers, meta-data files, everything. If I were in your situation I'd do this, because even if you deleted a few packages, the rest will be there and will have to be installed some way or the other. If you clear out everything you can start over by choosing only a few packages at a time and updating them.
If you just want to delete a few files, head to /var/cache/yum, there you'll find a couple of folders, each one containing a folder called "packages". You'll find them there. Some really large packages you can get rid of for the moment are kernel packages, OpenOffice packages, language packages, etc..