I think you might have better luck going to RSpec. To the best of my knowledge, rSpec will run both Test::Unit (and therefore shoulda macros) along with Spec files. If you were to move everything to shoulda, then I think you would end up rewriting many of the tests.
http://blog.davidchelimsky.net/2009/02/02/rspec-works-with-test-unit/
So it should just be a matter of moving your tests over to specs.
I have never tried to run shoulda macros within rspec, only the shoulda matchers. I don't believe it would be that much of an issue though.