Its interesting how many of the Existing SQL Server Service Broker examples that are publically available seem to have been written before the SQL Team put a security clamp down on messages and now just don't work. Even if you're just sending messages to services in the same database, you either need to:
a. Issue a CREATE MASTER KEY command in that database. Although Service Broker doesn't normally encrypt messages send in this environment, it might have to start doing so if you move the target service database to another instance while a conversation is on-going.
b. SEND messages WITH ENCRYPTION = OFF.
I'm not that fond of the second choice when the first is easy enough to do and makes it easier to work with when you start scaling the application out just one database. Less stuff to go back and fix later.
BTW, SQL Team member Remus Rusanu has put together a great Service Broker Troubleshooting Guide that you can bet is in my favorites list.