У нас была такая же история, когда мы решили пожениться. Если вы решили поженится в Германии, то Standesamt требует новое свидетельсво о рождении.
Мы решили эту проблему так: у меня мама живёт в Казахстане, она мне рассказывала какие у нёё проблемы возникли с моим свидетельством. дело в том что, они там вообще не выдают новые свидетельства, только в случае утери (и если даёт то только в личные руки). В итоге ей пришлось сказать, что мы его утеряли, так потом они потребовали заявление из милиции :) В итоге проблему решили деньгами.
Так или иначе, когда мы подали все документы в Standesamt, они нам сказали что это всё может длиться до 2 месяцев. Мы на всё это плюнули и поехали в Данию (с помощью одного немецкого агентства), зарегестрировались там без никаких проблем и заодно покатались по Дании :). Потом мы проставили апостиль после возращения в Германию (длидось всего 7 дней с почтой), и предъявили документы в Buergerbuero. Т.е. всё оказалось очень даже просто!
Ах да, фамилию нужно будем потом поменять в германии (в Дании нельзя изменить свою фамилию)