This is a limit on the ArcGIS Server service. Log in to your ArcGIS Server machine, and navigate to C:\Program Files\ArcGIS\server\user\cfg. Open the .cfg file for the service you are trying to access. Change the <MaxRecordCount> property to whatever you need it to be. Be sure to restart the map service and clear out the cache.
Actually, would you mind posting back about this? I would love to hear how the iphone sdk handles over 3000 graphics!