While receiving a plethora of improvements, iOS has remained much the same over the past 5 years since its debut. The homescreen is still comprised of a grid of icons, which for many, have now become strenuous. Having key settings, such as Wi-Fi, Brightness and mobile data several taps away has become a chore, especially when compared to Android, which makes excellent use of homescreen widgets.

What does Apple have to do to iOS in 2013 to rejuvenate this otherwise stale operating system?

I think a complete redesign of the UI would give it a nice rejuvenation. Even though that probably won't be likely next year, with Jony Ive now being part of the iOS team, we could see pretty much all of iOS's skeuomorphic apps disappear to make room for much more modern and user-friendly designs. In the past, Apple's use of skeuomorphism has been very good, but this is what is holding iOS back in terms of design.

I think that the skeuomorphism, while at some times is good, has been taken ove the top. The Find My Friends app is an example of poor UI design, and this is not normally to be expected from Apple. with Jony Ive having more power, we should hopefully see the implementation of a more innovative user experience, and one that doesn't solely rely on skeuomorphic elements to aid navigation.

2013 will be the first year of change, and gosh we need that! Android is innovating, WP has a total different and maybe even better usable interface. And where is iOS? Where it was in 2009, but slightly better. (yes, a bit to dramatic, but that illustrates my opinion)

With Jonathan on deck we'll ofcourse see the skeuomorphism removed like both Nathan and Frank said. And I like to think in the way of Frank, I'd like to see a new UI. Doesn't need to be totally new, but new would be fine, this one seems old-dated.

(1)

I think we won't see a fully new interface in 2013 or 2014. Because changing the full UI in one step would be bad for the number of sales. If they do it in a few steps than it's more of an advantage. Further, I think they are already working on this based on iOS6.1 as you can see over here at 9to5mac with the lockscreen music thing: 9to5mac.com . I'm not allowed to say more since I signed a NDA (I'm developer), so I'll just link you to 9to5 :) (2/2)

First of all I think skeuomorphic design in general is great, it makes the apps feel alive and lovable. Just reflect over how much attention Paper has gotten. (fiftythree.com)

That said I think Apple has to find its way back to "simple to use" and "it just works". I don't think skeuomorphic design has to goin order to do that. Hopefully Jonathan makes this happen!

Maps, iMessage, iCloud, Siri and Photo steams is great examples of things that do not work all the time. I think that Apple has to fix these fundamental apps/service before they focus on anything else.

I don't think it's a bad thing that iOS look and feel the way it did in 2009. One of Dieter Rams 10 principles: "Design should be long-lasting" (en.wikipedia.org)