A little late to the party I'd like to chime in here as well (document my solution for posterity)
I'm too using spring's rest template, also trying to perform a delete request with a payload AND i'd also like to be able to get the response code from the server side
Disclaimer: I'm on Java 7
My solution is also based on a post here on SO, basically you initially declare a POST request and add a http header to override the request method:
RestTemplate tpl = new RestTemplate();
/*
* http://bugs.java.com/view_bug.do?bug_id=7157360
* As long as we are using java 7 we cannot expect output for delete
* */
HttpHeaders headers = new HttpHeaders();
headers.add("X-HTTP-Method-Override", "DELETE");
HttpEntity<Collection<String>> request = new HttpEntity<Collection<String>>(payload, headers);
ResponseEntity<String> exchange = tpl.exchange(uri, HttpMethod.POST, request, String.class);