In Network World magazine there was an article that predicted a cloudy future for cloud computing. They listed a number of problems:

1. Data privacy - The article talked about the country border issues for some types of information. Although that's a constraint, I don't know that it is really what I'd call a problem. The people who create those services need to understand the applicable laws. What may be interesting is the liability if there is a violation. Is it the group that created the software, the group that runs the computer or the group that has the virtualized storage? They could be different and, I'm not sure that the laws have caught up with this reality.
2. Security - The security concern has been addressed by outsourcing entities forever. I don't believe this is new territory related to cloud computing.
3. Licensing - Not sure how much of an issue this would be either. You're going to be able to put commercial software on just any cloud out there. You are going to put it on a system that can run that software legally, in many cases a service affiliated with the software creator. My concern would be more about the integration issues between systems. A Tower of Babel condition could develop where the various services require different information and the translation and transport issues become a distraction from the actual business value generation. An enterprise architecture should address this kind of concern and this would not be coming from the Cloud/SaaS provider.
4. Applications - It is true that not all applications can make the transition to a Cloud. I've mentioned before that I believe a great deal of the cloud capabilities will be doing new types of work, not traditional application functions.
5. Interoperability - I'd have rephrased this concern as lock in. Organizations typically have concerns about getting locked into a service provider and having no way out. I'm not sure the Cloud and SaaS providers have figured this issue out. They may think of it as a feature not a liability.
6. Compliance - This is also an area the outsourcing market has addressed for years. The question that the SaaS and cloud folks need to address is: How can they support the individual industries needs?
7. SLAs - The Network World article talked about the concern about missing an SLA. I'd have focused more on the issue of end-to-end SLAs. No company cares about the fact that their data is peculating through the data center just fine if they can't get at it. This new market needs to address the end-to-end issue.
8. Network monitoring - this relates to #7, but rather than network monitoring I'd have focused more on business value monitoring. After all the reason these systems are in place is to generate value for the business.

I think their list is fairly comprehensive. The one area I didn't really see is the conflict between customization and standardization. The larger the client the more special that feel they are.