Don't discount familiarity and habit when talking about beginners' user experiences with computing devices.
I think one of the reasons some non-tech-savvy users consider iOS easier or more intuitive is what they're used to. Apple wasn't dumb. They had a successful launch of the iPod and got tons of people hooked on iTunes. Then they integrated the iPhone with iTunes, and they made the iPod into the iPod Touch. And they made the iPad like a giant iPod Touch. Whenever I've talked to iPhone users who've switched to Android or who are thinking of switching to Android, the topic of iTunes always comes up. "Will it work with iTunes? Will my music sync up? How about my podcasts and smart playlists?"
The answers aren't always easy. I happen to like iTunes myself, even though I haven't been a big iPod fan (I did own one of the earlier generations of it at one time). It took me a while to find what works for me on Android. I knew in advance that DRM is the devil, so even back in 2007 and before, I didn't buy songs from the iTunes music store. So no "protected AAC" files here. That isn't true, however, for all my friends. I know people who did buy those "protected AAC" songs. Also, for the first few years of Android use, I was perfectly content to manage things through drag and drop. After a while, I got tired of it, and I switched to DoubleTwist. That seemed like a bulky and slow solution. I kept doing researching and trying different solutions. I finally came upon iSyncr, which is great, actually. But it still takes a little bit of setup (and a small cost) over just plugging your iPhone in and having things sync with iTunes.
Also, I hate that there's no back or menu buttons on the iPhone, but it is literally simpler and less complex to have just one home button. Press it once to get to the main screen. Press it again to go do a search.
I don't think, however, that having four buttons is overwhelming to people. After all, the iPhone has that one main button, but it also has two volume rocker buttons and a power button. It might be disorienting to go from one main button to four main buttons, but it isn't too complex, just as going from half a keyboard to a full keyboard wouldn't be too complex. More buttons doesn't necessarily mean too complex.
I do believe in theory there is such a thing as intuitive interface design. But I also firmly believe that familiarity and habit trump intuitiveness every single time. If someone is used to having to press Home twice to get to a search, then simply pressing the Search button once will seem less intuitive, or at least more annoying, just because of what the user is in the habit of doing.