After your first contact, you can get any of your other contacts at any time. It may happen quickly, or it may end up feeling like an endless search that takes forever. Once you reach 150K xp, the chances of gaining a contact are greater. ((That's not 150K in each city.)) Ben changed the formula a couple years ago so that those unlucky detectives that were having so much trouble could feel a little hope again.
This also helps with those over seas contacts, not just your second contact.
Keep in mind if you are being particular and looking to gain a specific contact, it tends to draw out the process.