I don't think they charge fees for BTC withdrawals - I've withdrawn exactly
what's in my account before.
However if you have slightly more than 3.99995 BTC, their shitty software will round up to 4 and then give you that message. It's infuriating - Bitcoin is divisible to 8 decimal places, yet they only show four. If you only want to work in 4 decimal places, that's cool - don't let our transactions go lower than 0.0001 BTC and there won't be an issue.
MtGox and CampBX do this too. I whined about it in CampBX's thread, and apparently they're going to be fixing it and showing the full number. I think I complained to TradeHill about it, but it was around the time of the MtGox hack so it probably got lost in the mess.