I believe this is a Ruby 1.9 issue, and the current version of Shoulda isn't 1.9 compatible. There's a branch on GitHub that you can check out and use.
http://github.com/thoughtbot/shoulda/tree/ruby19
I also uploaded that version to Gemcutter for testing during the last Boston.rb hackfest, so if you want to install it:
sudo gem install shoulda -s
http://gemcutter.org
This 1.9 build from Gemcutter is by no means official, but it definitely is passing all of its tests on 1.9. Try it and let us know if it helps out.