Also, if you the coins you're trying to transfer are too fresh on your wallet there is a tax imposed regardless of the amount (they don't want people spending money that haven't been confirmed they own yet)

Are you 'gathering' a large number of very small transactions together? That tends to cause excessive fees. It costs about .001 BTC per source to gather coins into a transaction. So if you have a large number of transactions each around .001 BTC, it can be impossible to gather them effectively.

The solution is not to make large numbers of small transactions. It may help to let the coins sit still for a few hours.

It means the specific coins you use must have been in your wallet (have not moved) for a few hours. The client's logic in selecting which coins to use is a bit mysterious, and it won't always find the best combination of coins to use. It is not so much the client's fault -- it's also an issue that which coins are best depends upon what you plan to do in the future, which of course the client cannot know.

If you have a lot of small incoming transactions, you may need to do one "clean up" transaction. You can manually connect to a bitcoin client known to accept transactions with no fee, do a single "clean up" transaction, sending all your bitcoins to one address with a small fee, and then be very patient and hope the transaction gets to the client and then a miner picks up that transaction. It can take a day or so, but you should only need to do it once. Then just stop doing whatever created the mess in the first place.

Try this:
1) Create a new bitcoin address.
2) Backup your wallet.
3) Set your transaction fee very, very low (say, .005).
4) Start your bitcoin client with this on the command line:
-addnode=173.242.112.53
This connects a no-fee client run by Luke Dash Jr.
5) Create a transaction to transfer all your bitcoins to the new address you created in step 1. You may need to subtract .005 or so for the fee.
6) Go away for a few hours. If you're lucky, the transaction got into a block and all your bitcoins are now in one place. Let them sit there a few more hours and your problems should be solved.

If the transaction doesn't go through, you can revert to the saved wallet.dat file to undo the transaction.

It depends how you got those bitcoins. If you received them as a lot of small transactions, the consolidation transaction will have to gather them all which may make it large enough to require a transaction fee.

The minimum transaction fee was 0.01 until the most recent version of the client when it was reduced to 0.0005.  It will eventually be reduced further. Part of the deflationary nature of bitcoin is that, as bitcoins are eventually worth more and more, people will be transacting in smaller and smaller units.  The supply of bitcoins is finite, and on top of that bitcoins are occasionally lost/irretrievable (lost wallets etc), further exacerbating the deflation.

8 decimal places is not pointless; in fact it is VITAL to the long-term viability of bitcoins.  In fact, eventually even 8 decimal places will be insufficient -- fortunately the bitcoin network and client can be modified to transact in even smaller units if it is ultimately necessary (which it will be).

You risk losing money that way.  If a transaction looks like spam but doesn't have the required fee on it, not only will it not be included in blocks by the standard client, but it will also not be relayed through the P2P network by the standard clients.

Just pay the fee (0.0005).

Thanks for clearing that up

Yes, this is an important problem in the current implementation (considering that the intended network behaviour is to slow down low-fee transaction rather than having them get stuck in the client). A better implementation would be to throttle low-fee transactions at relaying time, rather than doing an all-or-nothing decision.

Until this gets fixed, the risk can be reduced by increasing the number of bitcoin protocol connections your client creates.