ТС сделать это можно и довольно легко. В любом случае для изменения персональных данных тебе потребуется написать заявление "изменение умышленно искаженных данных"

вариантов несколько:
1. еси у тебя в городе есть регистратор то лучше обратиться к нему. объяснишь ситуацию и расскажешь ему все как было, думаю тебе поверят учитывая что твоя ситуация соответствует представленному в первом посте примеру. ему и отдашь это заявление. а заодно придется получить перс аттестат и сделать это можно у того же регистратора.
2. если в городе нет регистратора то придется заверять заявление нотариально и после этого отправлять в Москву, в центр аттестации номер1. на имя Ромашева А.В. по адресу: москва а/я 130, 107140