Humm, I dont know what to tell you. I read your problem, and on my system (Kubuntu 8.04) I did the following to install Steam:
1) Build the latest version of WINE.
2) From the terminal as a normal user: wine msiexec /i SteamInstall.msi'
3) Follow the normal install routine, same as windows.
Did you use the latest build of wine? I am asking because of this line:
err:ntlm:SECUR32_initNTLMSP ntlm_auth was not found or is outdated. Make sure that ntlm_auth >= 3.0.25 is in your path.
This is probably your problem with not being able to login to Steam.