Ninemsn is about to launch a new look site. You can see the new site in beta here (screenshot below). It's not clear when they'll flick the switch, but they do have a few gremlins to work through, judging by some of the layout issues on the new front page.
They're overdue for an overhaul, and in my opinion the new look is an improvement. It will definitely shake up the competition ... as these things always do.
Another major site that's about to undergo a relaunch is The Guardian. The Guardian famously has kept its look and feel constant for years. I don't think it's actually ever had a redesign. So, as one of the biggest newspaper sites the new look will be the subject of much discussion. If you want to know what that look is, check out their new Travel section. The main site will be based on this design.
Personally, I like it. My only criticism is that the pale blue they're using for the link colour is a tad hard to read. But the layout is great, it's a much more effective use of space. I understand the launch date is some time this month.