Did you rebuild Stepmania after installing libasound2-dev and libpulse-dev, or did you build Stepmania before installing either of those? If you built Stepmania before installing those libraries, it probably built without support for them, and you need to follow the instructions for clearing the cache and rebuilding.
I did not realize that this was required. This fixed it. Thank you so much for your help!