Having worked with RESTful Web Services doing code-review and code-assisted app penentration-tests on RESTful apps that were over 3 MLOC, I can tell you that the problems outlined by John Wilander in REST and Stateless Session IDs is the dominant, growing problem. If you do not have this problem (which is a very big problem) in your RESTful Web Services, I would be shocked. It basically makes REST a security nightmare. If you follow John's advice and implement sessions with SSL/TLS, you have solved your first and primary problem. I picture this as a very large application development project.
Additionally, many components of such an architecture may be at risk. Chris Gates has done a lot of research on the public facing OAS, such as his recent column on Oracle Web Hacking, which includes a link to running code for Metasploit modules on his git repo. Sensepost released a tool (go-derper) and work against memcached at the last BlackHat-US/Defcon.
Finally, RESTful services most certainly have issues with SQL injection, DRO, CSRF, and XSS just like normal -- and the occurrence of stored versions of those injections would dominate direct/reflected attacks.
The problem with REST vs. SOAP is that SOAP usually produces a WSDL. REST could have a WSDL (with WSDL 2.0) or a similarly described WADL. However, this is unlikely, and without a list of entry points, it is difficult to test RESTful services. One would need either the source code, the documentation, or an existing test harness. SOAPSonar is a commercial option, while WS-Attacker remains one of the best current open-source options for testing.
I could see how some Firefox / Chrome plugins and/or web proxies (e.g. Fiddler, Burp, Web2Proxy) could also be useful, but this would require some significant investment in time to manually build test fixtures. If an existing test harness (e.g. soapUI, HttpUnit) is available to the tester(s), then these tools can be run through a web proxy, preferably one that supports XML/JSON like Web2Proxy, Web2Fuzz, AppCodeScan, and wsScanner (which are discussed in Shreeraj Shah's book, Web 2.0 Security - Defending Ajax, RIA, and SOA).
XML itself can be tested using tools such as Untidy, by the same author as W3AF, which has its own proxy called spiderMan (probably great for testing REST if implemented correctly). I'm not sure if Acunetix WVS (the most recent release, which was last week) supports proxying in the way that Netsparker Pro does (or Burp Pro Scanner), but if it does then Acunetix may be the best tool to test for the stored injections, as I hear it has great support for these types of checks. If anyone has a license for the full version of Acunetix WVS, please let us know. The AcuSensor technology would also be very useful here, as would HP Fortify PTA -- especially since the entry points are unknown.
In other words, testing RESTful services with black-box methods and technologies is bound to fail. The problem with identification of entry points, even with source code, is that many RESTful services are often configured and developed with code indirection technologies, such as several well-known Web 2.0 and Web Services patterns -- as well as Dependency Injection, IoC, AoP, et al. Worse, there are often several levels of this indirection, with no Views folder or other simplification. This makes it additionally difficult to utilize automated security-focused static analysis tools (e.g. LAPSE+, CAT.NET, Yasca, Graudit, FindBugs, CodePro AnalytiX, FxCop, Fortify SCA, Checkmarx CxSuite, Appscan Source Edition, Armorize CodeSecure, Coverity, Klocwork, GrammaTech, and many others). Cigital has a solution called ESP which is considered best-practice for large-installation, SOA-based Enterprise app portfolios (note that ESP is usually backed by several app pen-testers year round who know how to manually review source code as well as identify complicated runtime analytics of application layer vulnerabilities -- so it's not meant to be used solely as a factory).
In summary, it will almost certainly need to be manually reviewed with all major and minor build components available to the reviewers.