First, thanks for taking the time to report your problem here, so we can try to help. Though I can't reproduce the issue on three different Android test device I have, I logged a bug for developers to investigate this.
Mark gave you the same troubleshooting advice I would have suggested myself. Also, inside the app's Settings, there are a few other things I hope you can try:
-- "Clear the image cache" (this really should be the same thing you did in the device main Settings > Applications > Manage applications)
-- "Reset Preferences" (this should have been done when you uninstalled / reinstalled the app). Do Log Out/In again.
If this still doesn't allow you to use Photoshop Express online, let me ask -- are you able to upload to facebook or twitter?
Does this happen if you log into another Photoshop Express account?
Can you share some specific details about your device: specific model / Android OS version / carrier
Thanks for any info you can provide--it may help us validate and resolve an issue potentially affecting other users.
--Charlie
