I am in the same boat as you. I get the same message. "Your search may not return many results until you are fully connected" is also added to it.
Like you, I disabled the firewall, plus I re-installed it. The same message appears. One day I was down-loaded like crazy, and all of a sudden I'm waiting for it to fully connect. How do you not fully connect with a cable modem?