The interface on these Nokia phones is "fbus" and not a simple serial AT type command set. The nice folks at embedtronics refer to an AVR implementation of fbus, but I haven't been able to find it anywhere. There is definitely a trick to getting this going, and all the work I did to try to get this going is here:
http://1474orchard.ca/projects/?x=entry:entry110123-142726
http://1474orchard.ca/projects/?x=entry:entry110126-003505
In the end, I would recommend using a different phone -- I think the Ericsson and Siemens phones have a more tractable interface protocol -- or using a purpose-built GSM module. The latter is what I eventually did. While tinkering with fbus was interesting and all, I finally found that I just wasn't making headway.