Could it be that you are uploading large files when you see the difference in upload speeds? If the files you are uploading are large, Facebook has a lower threshold than Photoshop Express before it applies downsampling. This would explain the discrepancy in speed you are noticing.
You should be able to compare the same file uploaded by each application to confirm. If you are seeing something different, please let us know.
Thanks for your response, that makes perfect sense!
However, the files aren't that big, being from the inbuilt camera in the iPhone 3GS (3MP).
Upload time is several minutes from PS Express, 20-30 seconds from Facebook or Camera+.