First: Your class Foo is really a very bad approximation of std::string. I predict lots of memory leaks. (Search for "rule of three".)
Second: A pointer is not implicitly convertible to a unique_ptr object (for safety reasons). But the templated pair constructor requires the arguments to be implicitly convertible to the respective value types. GCC seems to allow this but it is a bug. You have to create the unique_ptr object manually. Unfortunately the C++0x draft lacks the following, very useful function template that eases the creation of temporary unique_ptr objects. It's also exception-safe:
template<class T, class...Args>
std::unique_ptr<T> make_unique(Args&&... args)
{
std::unique_ptr<T> ret (new T(std::forward<Args>(args)...));
return ret;
}
In addition, let's use the new emplace function instead of insert:
auto a = bar.emplace(1,make_unique<Foo>("one"));
emplace forwards both arguments to the corresponding pair constructor.
The actual problem you witnessed is that the pair constructor tried to copy a unique_ptr even though such an object is only "movable". It seems that GCC's C++0x support is not yet good enough to handle this situation correctly. From what I can tell, my line from above should work according to the current standard draft (N3126).
Edit: I just tried the following as a workaround using GCC 4.5.1 in experimental C++0x mode:
map<int,unique_ptr<int> > themap;
themap[42].reset(new int(1729));
This is also supposed to work in the upcoming standard but GCC rejects it as well. Looks like you have to wait for GCC to support unique_ptr in maps and multimaps.