I have had some problem with Pidgins “Waiting for network connection” (on my Linux-machine). Apparently the problem involved Gnomes NetworkManager. After a lot of searching I found an easy solution that worked for me. I use the -f option when starting Pidgin which tells it to ignore NetworkManager. You can add it in your Shortcut/Launcher if you don’t want to use commandline. If it doesnt work you might found a solution here.

If you are a Windows user I guess that the problem could be related to your networkconnection somehow.