I don't think the game is that complex. I do think, from personal experience, that it's a tough game for newbies because they can get screwed over pretty easily. When I first started playing Puerto Rico I was regularly reduced to despair by watching my hard-accumulated goods rot away on the pier. Until you've played a few times and have a feel for how the timings work, you'll have to be supernaturally smart to see this kind of thing coming. Many less hardcore gamers don't like this "school of hard knocks" route to success and will give up before they get there.
I've also always found that the buildings - which, let's not forget, are a bunch of nearly identical purple squares covered with tiny text - are impossible to "grok" the first time around. Again, you have to have played the game a bit before their differences and uses become anywhere near obvious, and it takes some stamina to get that far.
In addition, I've heard tell that experienced players get very frustrated with having newbies at the table... because in Puerto Rico you can get such huge advantages from the person sitting next to you producing goods at an opportune time for you, someone acting cluelessly can create a huge swing in the power balance of the game. So not only is the game not much fun for the hapless newbie, it may also be not that much fun for those trying to teach the game to beginners!
But after all that doomsaying, I do have to say that Puerto Rico is well worth it once everyone gets the hang of it. I'd just recommend building up to this level of Eurogame (pretty much the top tier, eh?) in incremental steps, so no one's head explodes from coming to it direct from The Game of Life :D