I had my identity stolen several years ago and am still recovering from it. While most of it has been resolved, from time to time I find issues that have significant impacts. I even tried to get a new social security number but was denied because the amount of damages was not significant enough to trigger a reissue, although I have no idea and was never told what the trigger amount was.
The best advice I can give you, is to do everything by snail mail. Send certified letters (you can even do overnight if you have a few extra bucks for quicker delivery) and keep track of everything. File a complaint with your state attorney office (most have departments dedicated to working with you on this). Send copies of everything to the state attorney as well as the credit bureau. Snail mail takes longer (depending on how you send from a day or two to receive all the way up to a week), but for some reason it actually escalates your issue and does result in quicker resolutions than fighting with people on the phone. It sounds like you caught it fairly quickly. Call the other bureaus as well (Transunion and Experian) and put fraud alerts on your file. It is simple to do with a quick phone call. They will also send you a free copy of your report from them so you can double check. Finally, if you have a good credit card company some will help you with resolving the issue and dealing with the bureaus on your behalf. It is in their benefit to help you if they can.
Good luck.