I got a problem with clang today: it complains cannot find standard C++ header files.
So I used two magic options: clang -v -E, which outputs details about how it tries to find the header files. This reveals that clang finds in /usr/local/c++/4.4.x, but not including /usr/local/c++/4.5.1, which is my only version installed together with GCC 4.5.1.
So, my solution is simply sudo apt-get install g++-4.4. (Note that is not enough to install gcc-4.4, because that does not bring you C++ header files and libraries.)