How are you calling the imaging web service? If it's client side it may be more an issue with the client system resources than the server. I'm assuming that your CPU profile is on the system calling the web service, as opposed to the server.
The issue with images and the web services is the sheer amount of data. With the lists web service, attachments have to be broken down and encoded into a binary string to be sent to the server. This process is very intense if you're running it client side. Your holdup is probably not the server dealing with the data, but rather the client system struggling to encode it all; especially if you're seeing CPU or memory spikes.
I had a previous requirement to bulk load ~5,000 documents into a document library. The average size was about 5mb, but some were as large as 30mb. We ran into issues with anything over 10mb or so hogging the resources on the client system. It took us about 2 hours to run the migration. Even a 640x480 image still contains a lot of data, and once you encode that out to binary it's a lot to process. For a web service, client side, I'd say your time's aren't that bad. If you can find a machine with more resources to run your migration tool on it'll probably help your cause a bit.
How is your application written? We found some performance gains by encoding multiple files at once and pushing them to the server in a chunk (say maybe 10 at a time), as opposed to doing it one for one. As James pointed out though, if you're end game is to attach them to a list item, I'd just use the Lists.AddAttachment operation.