Because of Steam Client's inconsistency at connecting to it's servers, I had took a long time tracking down the culprit.
Until one of the computers on the LAN went offline. It was apperently running utorrent.
Even though it wasn't using bandwidth heavily, it might somehow intefrere with Steam's ability to connect.
I'm not entirely sure yet, even though I was able to connect to Steam 2 times now after that PC with utorrent went down.
I'll post back after I further succeed at connecting on Steam.