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

or

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?

cheers

Andy