See this transaction here: http://blockexplorer.com/t/37LGcZAis7 in this block: http://blockexplorer.com/b/119132

The transaction was 0.225 kB, one input, one output and total block size was 4.07 kB and I was told that it needed a 0.01 BTC transaction fee. WTF?