I assume by cloud agnostic you mean agnostic to the particular platform you're running on, such as GAE, Amazon EC2 or Azure and you wish to write one, deploy anywhere.
In theory, that should be possible if all cloud providers support the same languages. As far as I know GAE supports Python and Java. Amazon EC2 can use just about anything on the actual server itself and Azure is a wholly .net platform. So the actual processing side of things i.e. writing the queue web service and processing unit(s) might be difficult.
Another barrier is that there isn't a common unified API for calling on cloud computing services. The implementations are different across GAE/Azure/EC2 anyway, so the methods their API exposes are all different and to that end, your front line code will need to know which type of API it is calling to control the cloud computing resources.
However, by nature web services are loosely coupled. Meaning provided you go to the effort to abstract the resource control so that you can create an instance on whatever cloud you want, if that new instance is yet another unit handling a web service's input / computation and the web service exposed is the same on GAE as EC2, for example, there is nothing stopping the two talking. Similarly, provided you use some form of web service / protocol between instances, you should still be able to talk to other instances over the internet across computing platforms. That said, in doing so you'd expose your internal application's data to the world at large and thus introduce a security risk.
I'd agree with disown: Java is a pretty good way to go. There are a huge number of EJB containers out there and even more web service servers like Tomcat. I'd guess EC2 supports it (well, it definitely does but whether they run Tomcat/Geromino rather than the IBM editions and what the charges are like I don't know). GAE sounds limited based on this blog post - whatever Google are doing on the backend they've engineered something very strange.