Hello Nanette,
the webside with the german telephone book you got from our friends.
The genealogical working group for the Magdeburg area you find under:
http://khv-magdeburg.de/agfgig/06.htm
e-mail: Horst.Koetz@t-online.de
They have a name file with 50000 names.
Good luck for finding your "Urgrossvater"
H. Miethe