<p>I'm starting a project using a Restful architecture implemented in Java (using the new JAX-RS standard)</p>

<p>We are planning to develop the GUI with a Flex application. I have already found some problems with this implementation using the HTTPService component (the response error codes, headers access...).</p>

<p>Any of you guys have some experience in a similar project. Is it feasible?</p>

There are definite shortcomings of Flex's ability to act as a pure RESTful client.
The comments below are from this
blog
:
The problem is HTTPService class has
  several major limitations:
Only GET and POST methods are supported out of the box (unless you
  use FDS and set useProxy attribute to
  true)
Not able to set request headers and there is no access to response
  headers. Therefore I am not able to
  access the response body in the case
  of an error.
It HTTPService gets a status code anything other 200, it consider
  an error. (event 201, ouch!!). The
  FaultEvent doesn’t provide information
  about the status code any response
  body. The Flex client will have no
  idea what went wrong.
Matt Raible
also gave a
nice presentation on REST with Rails, Grails, GWT and Flex
that have some good references linked from it.
Whether it's feasible or not really depends on how much your willing to work around by proxying, etc.