I came up with a solution.
I was not able to solve this issue as it stood. The old format for jboss-messaging.sar/*.xml doesn't port to the later version.
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/*
The jboss messaging queues and topics are now successfully deployed.
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>. So switching over to the microcontainer approach worked nicely.