The "Polymorphic Function Object Wrapper", a generic function pointer type (library change, based on Boost implementation). Basically, a class which implements operator () and allows object/method pairs as well as generic function pointers to be called. [Probably a good thing to put in; lots of people, including me, have rolled our own...--ScottJohnson]
Tuple types. (Proposed as a library addition; though several core language changes that would be beneficial are noted).
Additional math functions ("special functions"), present in C99 standard library.
Enhanced member pointer adapters
General-purpose smart pointers. (Another thing frequently subject to RollYourOwn)
Improved random-number generator libraries
Reference wrappers (ugh).
Enhanced binders (?)
Hashtables. (Most STL implementations implement these anyway...)
Now a few other things that would be useful, and "relatively painless" to do. (Relative is a relative term, of course).
Improved compatibility with C99. While I don't feel it is necessary for C++ to be a superset of C; they should have a common compatible subset. BjarneStroustrup advocates this as well....
Alternate ctor/dtor syntax, such as allowing a ctor/dtor to be named "this" rather than the name of the class. Would make it possible to write constructors for anonymous classes.
Class initializers, ala Java, for initializing static class members
An official "object" class, the supertype of all classes with virtual functions. (For backwards compatibility; existing classes would not be redefined as subclasses of object; however the intent would be that ANY class with a virtual anything would be a subclass of object in the future).
Enhancements to the I/O library to support such things as networking, asynchronous or unbuffered I/O, pending on multiple file descriptors (selection), and all sorts of other stuff.
Raw string literals, a little like Python's but with flexible delimiters: R"delim[anything here]delim" where delim is optional and can be almost anything.
Previously in the "you're dreamin'" category below, but actually being pursued for C++09:
Garbage collection. (Optional of course, this is CeePlusPlus).
I don't see the benefit of having this in the language standard. There's a number of existing implementations available, why would you want to have it be a mandatory part of the standard and the library?
Support for synchronization and multi-threading as part of the language.
And in the "you're dreamin'" category
Reflection and introspection capabilities
Dynamic method/member lookup, similar to a Smalltalk message send. In other words, in order to call a method "foo" on an object, I don't have to cast the thing to a class which has "foo" in its interface. I can simply (using a different syntax) invoke foo, and if it succeeds it succeeds, otherwise an exception is thrown. (See Java for an example of HowNotToDoThis?).
This, the previous item, and the Object superclass would all be related and all have the same set of problems, which is how to implement this in a way that preserves the semantics of the language. The extra metadata you'd need to carry around about objects alone would be a huge loss. Sometimes it's a reasonable tradeoff but it's not something you should retrofit into C++. If you really want these features, then you should use a language that has them, not change C++ to be more like that language.
Something approximating a lexical closure. C++ comes close with functors (just as Java comes close with inner classes), but closer would be nicer. To keep this simple, they don't have to be first-class types--if you want a lexical closure to outlive its referencing environment, you probably want an object instead. Oh, and a nice easy syntax to make these, similar to Smalltalk blocks.
Robust base classes, which use robust lookup techniques (e.g. hashtables) rather than fast-but-brittle ones (computed offsets). Would fix a lot of instances of the FragileBinaryInterfaceProblem.
This is the same thing as above - you aren't talking about changes to C++, you're talking about making a new language that looks like C++. Use the new language instead.