I was not able to solve this issue. So what I did was instead of using the jboss-messaging.sar files I had working on JBoss 4.3.0.GA EAP as the starting point, I copied the JBoss 5.1.0.GA EAP's server/all/deploy/messaging into my server/customconfig/deploy/ folder.
I started JBoss5, made sure it still starts up. It did.
Then I just applied all the non-default settings I had in my jboss-messaging.sar/*.xml files and then applied them over to the files in server/customconfig/deploy/messaging/*
This worked fine. The actual problem had something to do with that fact that I was trying to specify the mbean for SecurityStore in the messaging-service.xml file as an mbean. But now I believe it is a microcontainer <bean>.