I was in Montevideo and Punta del Este in February as part of a longer South American trip, and loved both of them. Out of the trip, they were probably the two places I was least looking forward to, so it was truly a pleasant surprise and I would love to go back to both of them. Of course it probably helped that both places involved visits to wineries for me.
One of the things I had trouble wrapping my brain around in Montevideo was that, while there were beaches and it looked like the ocean, you really were looking at a river.