Going from C to C++, there are two things to pick up: general OOP and C++-specific concepts.
Due to the complexity of C++, I found it easier to pick up general OOP through Smalltalk and Java. It is obvious that the designers of Java and C# looked at C++, got rid of conflicting features and kept only the useful OOP stuff.
I agree with you that STL syntax can get nasty rather quickly. In general, I can code up something much more quickly (get it working) in Java or C#. But I agree with you, in general, C++ has a very steep learning curve. Even the implementors have a difficult time getting things right (look at the deprecation of auto_ptr<> as an example).
However, these days, I am coding in C++ full-time.
Why? Efficiency. I want control over memory, garbage collection, etc..., while being allowed to do encapsulation and polymorphism when I need it. That being said, I use a very small subset of C++'s features - probably 25% - it's too easy to sucked into trying to learn something new in C++ and get distracted from completing a project.
IMNSHO, Java has some serious design flaws, so I avoid it whenever possible.
Keep in mind that C++ was designed to be all things to all people -- it is a multi-paradigm language. You can use it procedurally, object-orientedly, generically, functionally, et ceterally -- mix and match at your pleasure. It isn't the language that is complex -- it is the myriad ways you can use it.
As a newbie programmer, learning C++ as my first language, everything seems to be the way it should be.
I guess it is like learning another language (not programming, i mean language, eg. English). As a baby, you learn your native tongue and you see nothing wrong about it. You don't pick up on any peculiarities about the language. Everything is as it should be because you have no other languages as a reference point. However, of you learn a new language, you now base everything off your native tongue and you start wondering why other languages are so strange and foreign.
IMHO, C++ is a complex language, in the sense that it is "full of surprises".
*How often do you write C++ code and it compiles and runs as you expect in your first try?
For me personally, this happens much less often in C++ vs Java, C#, or Ruby.
Now, the irony is, C++ tends to attract some very smart programmers (and many who might not be smart enough to use C++ - look at Linus Torvald's comments - I think he has many good, valid points). So my *comment above may not apply to some of you C++ gurus posting here. I used to have a coworker who would stare at C++ code when debugging - he rarely went into a debugger - he was one of the sharpest developers I know.
Nonetheless, this doesn't take away the fact that C++ is a "non-trivial language", like *nix is a non-trivial OS. In this sense: I can spend 5, 6, 7, 10 years learning C++ and *nix, and it will still surprise me with new "features". Maybe this is more true of C++ than *nix. I am comfortable to say I know C or VB or even Java - I don't know if I will ever be comfortable to say I know C++.
So I think all of OP's pains with learning the language are valid. STL is kind of a nasty case because it looks like an academic exercise rather than something that is useful for developers. If you don't believe me, take a look at C# or Java and see how you can do the same with less pain. STL reminds me of X-Windows, where flexibility/complexity won over simplicity. When a Java programmer comes up to me and says he can do the same in Java, I agree with them 95%+ of the time.
But after all this, I still use C++ and I enjoy programming in it... ...if and when I can get it to do what I want it to do.