I am having the same problem. I've installed SQL Server 2012 on a Windows 8 machine. SQL Browser is enabled. Remote connections are enabled. Firewall has rules for SQL Server ports etc.
My SQL Server is called DELL-D830\SQLEXPRESS
My Server is on 192.168.200.149.
If I do sqlcmd on the machine local to the SQL Server, no problem, everything works fine.
If I do sqlcmd from a remote machine using command
sqlcmd -S DELL-D830\SQLEXPRESS -U andy -P andy
sqlcmd -S 192.168.200.149\SQLEXPRESS -U andy -P andy
Have also tried
sqlcmd -H 192.168.200.149 -S .\SQLEXPRESS -U andy -P andy
With all commands I try I get the same error messages as reported at the start of this thread.
Any ideas what I've missed or are there any known problems with MSSS on Windows 8?