Actually, according to another walkthrough I just checked, it is asking Grace for your messages that puts the police station on your map. In games like this, sometimes it's hard to know exactly which action causes what result!
Another thing to realize is that Gracie has more than one message for Gabe. Be sure to check with her every day and to read the Times Picayune every day for leads you will need through-out the game. It is usually a good idea in this game to ask about every topic until the characters start to repeat them selves.