yea, once i had to leave a wallet open for 5hrs to find any connections, after that every restart of the wallet got instant connections.
with BTCD i never had problems tho, but it guess you have one of those moments