If you make mention of a type in a header file, then you need to have already declared the existence of that type. In your case, you make mention of the class std::map<...> in your header file, so the compiler has to have at least a little bit of a clue about this class. A forward declaration might be good enough, although from memory, I can only guess what a templated forward declaration would look like. But try putting this (or something similar) near the top of your header:
namespace std{ template<class Key, class T, class Pred = less<Key>, class A = allocator<T> > class map;}
Normally, however, including <map> at the top of your header is perfectly fine, especially since <map> shouldn't be changing frequently, and thus shouldn't impact your compile times by being included in a header which gets included by multiple cpp files. But you mention that you have problems when adding <map> to the header. What are those problems, in more detail? Because this method should work, and is probably the preferred method for this situation.
Also, as for just including <map> in your cpp in the past, that's probably because you never needed to mention the std::map type in your header. As long as all use of the class is restricted to the cpp file, you only have to include the header somewhere in your cpp file. My guess is that this is probably the first time you had functions that pass std::map objects around.
"We should have a great fewer disputes in the world if words were taken for what they are, the signs of our ideas only, and not for things themselves." - John Locke