Yes, public queues only work on domains.
I have used MSMQ in Windows 2003, but not in Windows 2008.
I think they have changed the way to build public queues for windows 2008(public queue are defined/stored in Active Directory under the computer object hosting the queue)
Note: I found an article that implies that you can use private queues with WCF in windows server 2008, (but I have not implemented in windows 2008)
http://dotnet.dzone.com/news/msmq-wcf-and-iis-getting-them-