I was under the impression you could send any size transaction with any size fee or no fee, and it would depend on which miner processes the next block whether it would be confirmed in that block or not. (And that if the next miner didn't accept it, it would then have a chance of being confirmed in the next block, and so on.)
That assumption is true. It is up to miners to integrate any transactions they wish to the blocks they're attempting to solve. I think that warning is an implemented (but not enforced) guideline about transaction fees in the standard client. He can still try to submit the tx for free, and chances are one of the miners that integrate tx regardless of fee will take care of it(~99% of the network right now).
What this warning shows is how much you'd be expected to "tip" in order to have that tx processed in the late future.
A similar thing happened to me before when someone accidentally sent me 100 1-BTC transactions. I tried sending them back all at once, and it seemed to me that it was not possible to send them without the transaction fee. mestar's post above concurs:
If you click "No" that you don't want to pay the fee, the transaction is cancelled. I ended up paying the guy back with two free 50-BTC transactions, but it still seems like something is wrong.
And I agree with Gandlaf - it is very confusing if the transaction fees can't be anticipated by the amount of the transaction. If the user can't easily tell whether he has 100 individual bitcoins or 100000 of .001 bitcoins, it's going to be frustrating and confusing for him to try to send without knowing the number of kilobytes the transaction will be and therefore how much of a fee he should pay. How are merchant-customer agreements on fees going to be set if they are unpredictable?