Ran into an issue on my newish Windows XP x64 dev machine today; my public queues were missing completely from Message Queuing! The dev team have all got new installs from the same image and I'm the only one with the problem; so I'm not sure what I've done :/
So I did some digging... Message Queuing integrates with active directory but due to an orphaned object my message queuing went into workgroup mode. There is this article on the Microsoft site that may help, but I solved the issue by uninstalling and re-installing Message Queuing.