I had this same problem. There's a file or program or dll or SOMETHING included with the Internet Explorer 6 installation that will help WINE conenct to Steam's servers.
The strange thing is, I used WineX to install steam and I have steam installed to a WineX directory (~/.transgaming/), but Winex won't run Steam correctly so I have to run Steam with normal Wine to get it to function.
- Also, I used Wine 20031212 and not the newer 2004 version.
A tutorial I found very helpful, but not a solve-all, is located here