This probably really belongs as comments in several of the above posts, but I don't yet have the rep to do that, so here goes.
I think it is interesting that a lot of the pros and cons often cited for SOAP and REST have (IMO) very little to do with the actual values or limits of the two technologies. Probably the most cited pro for REST is that it is "light-weight" or tends to be more "human readable". At one level this is certainly true, REST does have a lower barrier to entry - there is less required structure than SOAP (though I agree with those who have said that good tooling is largely the answer here - too bad much of the SOAP tooling is pretty dreadful).
Beyond that initial entry cost however, I think the REST impression comes from a combination of the form of the request URLs and the complexity of the data exchanged by most REST services. REST tends to encourage simpler, more human readable request URLs and the data tends to be more digestable as well. To what extent however are these inherent to REST and to what extent are they merely accidental. The simpler URL structure is a direct result of the architecture - but it could be equally well applied to SOAP based services. The more digestable data is more likely to be a result of the lack of any defined structure. This means you'd better keep your data formats simple or you are going to be in for a lot of work. So here SOAP's additional structure, which should be a benefit is actually enabling sloppy design and that sloppy design then gets used as a dig against the technology.
So for use in the exchange of structured data between computer systems I'm not sure that REST is inherently better than SOAP (or visa-versa), they are just different. I think the comparison above of REST vs SOAP to dynamic vs. static typing is a good one. Where dyanmic languages tend to run in to trouble is in long term maintenance and upkeep of a system (and by long term I'm not talking a year or 2, I'm talking 5 or 10). It will be interesting to see if REST runs into the same challenges over time. I tend to think it will so if I were building a distributed, information processing system I would gravitate to SOAP as the communication mechanism (also because of the tranmission and application protocol layering and flexibility that it affords as has been mentioned above).
In other places though REST seems more appropriate. AJAX between the client and its server (regardless of payload) is one major example. I don't have much care for the longevity of this type of connection and ease of use and flexibility are at a premimum. Similarly if I needed quick access to some external service and I didn't think I was going to care about the maintainability of the interaction over time (again I'm assuming this is where REST is going to end up costing me more, one way or another), then I might choose REST just so I could get in and out quickly.
Anyway, they are both viable technologies and depending on what tradeoffs you want to make for a given application they can serve you well (or poorly).