Why did you choose to split your image into tiles? What version of the software are you using? From 9.3.1 and on you can publish a raster dataset as an image service with ArcGIS Server. If you need to create a cached service, you can open ArcMap, add the raster dataset as a layer, save the mxd and publish the mxd as a map service, then cache the map service. At 10.1 you will be able to cache an image service.
I'm not sure I understand this limitation completely. But it looks like the application using the image service can only access PNG images that are 256x256. If this is what's happening, then it should be up to the application to make a request to the image service that specifies that size and format. This is very easily done in a Web application using REST. See this example:
So what I'm saying is don't create tiles from your source data. Use the image service to serve a tile(s). Because even if you tile the source data, the image service (via the mosaic dataset) is going to merge them to produce the image that is requested.
Or are you saying you have to create png's that are 256x256 and serve them as a single image service. If this is the case, then create a mosaic dataset, add the data and publish it as an image service. However, you cannot create a cache from an image service in 10.0. (which is why I suggested using a map service). But then you will have an image service that uses all these tiled images. To publish an image service from a mosaic dataset you need the ArcGIS Server Image Extension - which is just a license for ArcGIS Server.