In general the service that you are using has to have exportTiles operation enabled. This is controlled through service management functionality either in ArcGIS Online or in Server. The default basemap service doesn't expose this functionality but there are service that support the operation.
For example World Street Map (for export). These (for export) services aren't meant to use as a basemap but they are used to provide exportTiles functionality for the normal basemaps which should be used when using the online based services. You can find other basemaps also from ArcGIS Online.
Another thing that you might be hitting is that there is a limit how many tiles the services will return at maximum which defaults to 100 000 tiles. If the area that you are requesting offline is too large the operation will fail.
If you cannot control the tiles returned, you might want to request the tiles in several parts so instead of requesting one huge area, you can split it into 4 or so section and request them separately.
Hope this helps.
