For ActiveMQ 3.x/4.x
As Matt reported
its possible that there is a race condition in your application; are you sure you had created your consumer and called start() on the JMS Connection before the producer started publishing messages?
Another option if startup race conditions are a problem is to use durable messaging.