I always pay fee and I paid 0.0002 for this transaction. It was not my first transaction with 0.5 BTC or higher. But I have never waited longer than 10 to 15 minutes.
I had to wait about 45 min to get first confirmation. It's a significant increase compared to a month ago, but i'm sure they'll fix it somehow and soon.
A year ago the same thing used to take 10 min!
Pay the fee and you won't have any problems. I just sent some BTC and paid the 0.0001 fee and it was confirmed in minutes.
Is the network still overloaded?
Just made a transaction, paid 0.001 fee and it was included in the next block, also received a transaction that was included in the next block with a 0.0003 fee, I guess I've overpaid.