The web is the biggest thing that changed all that. People have grown accustomed to sites that all look unique and have navigation in slightly different places and in all sorts of styles. Menus, buttons, links, the all look different depending on the site. But as long as it looks good and is well designed, people figure it out. It's probably even a skill we keep improving: getting better at figuring out a new website.
And that's something the iPhone and Android continued. I've even bought a few apps (like Weightbot) purely because their well designed UI got some press and I wanted to check them out.