A BDD framework could work but it might prove to be fragile considering the possibilities of what might happen between selenium, your app using the api, and whats going on inside your api.
There is a great php way of doing this
http://docs.guzzlephp.org/en/latest/
If you like other languages you could use Mule ESB to do testing against web service api. I have found it to be very good at running custom anything against a service or anything http. If you like groovy or java Mule ESB is perfect for getting directly at an endpoint to pull the reponse apart and fire off valid and invalid requests. It has a pointy clicky interface for a large variety of possibilities. If your api returns xml you have plenty of ways to parse it directly. It works well with JSON too. Even if you created your own format for the data response you can just dig into that fairly easily. Guzzle gives you much of the same but in a php curl friendly way but no pointy clicky stuff.
If your language and framework you are using for your REST api has a decent unit testing package then do that too especially where it makes sense. I know you are using php and I hate unit testing in php but sometimes you can't do it any other way to verify certain methods are correct when you want to protect certain methods.
I have seen successful api test suites created using a javascript testing framework like Jasmine or qUnit as well.
It all depends on what you are comfortable with and nature of what is going on with your api and what features of your api you would consider are important to cover.
