Played 
I've built one of my test servers with SQL Server Express 2008 w/ Advanced Services. On a whole load of our servers I use SQL Express for local installations and SQLCMD.EXE works well as a good way to run scheduled backups. It's done this way because SQL Express doesn't support SSIS (SQL Server Integration Services), the component required for scheduled tasks. With SQL 2008, however, SQLCMD.EXE didn't work for me when I tried to setup scheduled backups. Here's how I fixed it ...
The instance in question has the default name of SQLEXPRESS. Obviously this means that to connect to the server you need to use SERVER\SQLEXPRESS - that works fine from Management Studio and from the Java application installed on this particular server.
When using SQLCMD.EXE from the command line the full error message looks like this:
Some Googling suggested that this problem could be caused by one of 2 things. Firstly, that the SQL Browser service isn't running - on my server it was running. Secondly, named pipes aren't enabled in the SQL Server Configuration Manager ... on mine they are. Hmmm.
I've had problems in the past with named instances of SQL Server so I had a look at the properties of the named pipes configuration and, sure enough, it said \\.\pipe\MSSQL$SQLEXPRESS\sql\query. That *looks* ok, right? Yes but it's the cause of the problem.
I changed the named pipe to the following.
Voila! SQLCMD.EXE now works from the command line meaning my scheduled backups now work too. Not being a full-time DBA I'd put this down to a bit of a fluke on my part although I then found an article by Jesse Johnston that confirmed the same steps worked in their situation too.
Problem solved!