As for the suggestion that "This is a PC release and PC releases always have problems like that", I'd disagree. I've played a good many PC games, even some new releases, and America's Army 3 is the only recent one I can think of with so many immediate problems, or at least, online ones.
I'm sorry to make so many updates, but I keep adding information. I just tried the game in Windows Vista RC 64-bit, on my other partition (which I haven't even used in a while, making it HIGHLY unlikely that this is a virus issue). I was able to run the game, and get into an online game (one of them...several timed out, and the one I got into had like 1-2 second lag until anything worked like jumping or ironsights aiming).
But the friends list problem STILL remains. Here are three screenshots I took, from a video I recorded of part of my screen. Here's what happens in order when I try to add someone as a friend and then HOVER over the OK button:
Also, verifying the game cache in Steam didn't help. Creating a new GameSpy ID from within Borderlands itself didn't help.
To recap for anyone who missed the other posts, Google doesn't have this error anywhere on the internet, turning the firewall off doesn't help, I'm using Avast and it doesn't have a firewall, direct connecting myself to my cable modem instead of through a router doesn't help, etc.