An extra thread(s) to handle the callback processing is a good idea. As mentioned above, having your callback push a message onto a thread safe queue and another thread consuming/processing the message works great.
Another threading scenario that may work for you is to just start additional threads on the io_service. These additional threads will make it possible to process several handlers at the same time.
const int max_threads = 5;
boost::asio::io_service ios;
boost::thread_group thread_group;
for (int i = 0 ; i < max_threads; ++i)
thread_group.create_thread( boost::bind(&boost::asio::io_service::run, boost::ref(ios)) );
The correct solution really depends on what the application is doing. If this is a TCP connection and the messages need to be processed in sequential order consider using the producer/consumer queue. If the messages are independent of each other and do not require that they are processed in order then this approach is suitable as well.
If its a UDP connection then all bets are off anyway because the ordering of the received messages is not guaranteed.