I had a few people come to me with this problem. (I am an iOS Developer, and my friends and family know this, so they all come to me) The people with this problem all had iOS 5.1's public release on an AT&T iPhone 4S. Simply, a hard reset fixed them all. (One was stubborn, but it worked after the second hard reset)
If you are still within your warranty, including an extended AppleCare warranty, Apple should replace your phone for this problem. That would be the first step. Otherwise, try backing it up and restoring from the backup, and if that doesn't work still, contact Apple or an Apple Authorized Service Provider... although this will almost definitely cost you a bit.
It may just be easier to get the IPSW for iOS 5.0.1 out of your computers stored files, and install that by Option-Clicking on a Mac (I'm not sure of the Windows Command, but it is doable on Windows too) and locating the old IPSW. It should install fine, and if it doesn't, put your phone into Recovery Mode and try again. The save location for old IPSWs on your Mac or PC can be found by searching your files, or you can do an online search to find out where they are. As far as I know, iTunes should hold onto these files for you on whatever OS you have. Make sure you are using iTunes 10.6 as well.
If you do all your updates OTA (Over The Air) with Software Update on your device, see if you can get the file from a fellow iOS user. Anyone using iOS 5 that got their device before it came out and updates from iOS 4, should have at least the original iOS 5.0 IPSW file. Of course, you would need the one for your phone, and the 4S shipped with 5.0, so you'd have to find the 5.0.1 IPSW from a friend with a 4S.
I'm sorry the answer isn't more simple, but Apple doesn't always make it the easiest to find old OS versions. They want users to stay up-to-date as much as possible. My last idea would be to find a developer who can access the archives of prior releases; as long as it is a public release version and not one of the developer-only betas, it should be okay under their License Agreement with ADC to share the public release files.
I hope this helps.