You could turn on cascade update on the existing relationships for SSN's. That would at least solve the immediate problem of what happens when the wrong SSN is entered.
Since downtime is an issue, I would add all the FK's to the approriate tables. Next write a series of update queries to update the FK based on the SSN. Put those in a macro.
Take a cut of your frontend at this point for later use. Modify a transitional frontend so that the screens populate both the new FK and SSN simulatenously using the afterupdate events. Since SSN is dominate at this point you might run your macro somewhat regularly until you can cut.
Once that is done and in production, I'd look at how many queries there are and take a hard look at whether it is worth manipulating them manually or programmatically. Be sure to change this in the cut frontend because you don't want to have to remove the update code later.
Once your queries are update. Try changing all the names of your links and replacing them with queries of the original name that select everything but the SSN FK's that are becoming defunct and of course make sure you turn off the 'feature' that cascade updates name changes first. Test. Once you are clean, relink the orignal tables (delete the renamed tables and queries first). Change back the autocorrect 'feature' if desired (having done most of my development in Access 97 before this feature it bites me more than saves me).
Once you modify your schema, you should be ready for production.
That is the cleanest process that comes to my mind at it is a lot of work at that.
Because SQL server supports cascade updates at least through triggers (I think SQL 2005 has a more native support) and ultimately comboboxes should be selecting the key with limit to list, I have to wonder if it is really worth it. Clearly there is value in doing it but what is the ROI? This is of course for your consideration only. I have a bad system myself that will be rewritten...
The alternate approach is to scrap the whole project and rewrite it in a new platform considering the existing schema and using queries to map the data. This may prove easier in the long run, especially if you are strong in SQL and the target Application platform (VB.NET / Access etc.)
One more thought... I personlly don't care for ADP's with native SQL support. I think you give up too much from abandoning the MDB frontend.
That's all I have.