Have a look at http://code.google.com/p/sserial2mobile/
-- library for 'speaking' to a motorola phone by using AT commands.
I have an old SonyEricsson z600 that I was using in a project.
Using the above library, i was able to send SMS messages and read phone status etc.
Nokia phones might work - have not tested it.
However, you should try using an older phone, eg. the Motorola in the example, or an old SonyEricsson phone, as they have standard RX/TX pins in the connector.
Newer phones tend to have USB only, making them impossible (or very hard) to talk to with the arduino.
I think I read somewhere that there is Rx/Tx available on nokia phones (usually hidden behind the battery somewhere), but it may not be possible to use AT commands to talk to the phone that way.