I am not using either of the recommended STL implementations - is that my problem? I thought that since I was able to compile my code that std::string was built-in but that I was doing something wrong (like not including some windows library).
I think I found the problem - I had changed the order of the include directories. When I put them back to their original order, my std::string code links fine.