I got the below message when trying to upgrade a service
The AppExchange Application or component you have selected is not yet available on your instance of salesforce.com. Please check back in a few days to retry the installation. Press the back button of your browser now and bookmark the AppExchange Directory page so that you can find it later.
I uploaded a new version of my service a few hours ago and it seems that I can not use it (I tried to upgrade my customer's service). I guess there is a certain delay, did you encounter this error?