"The developers I was working with also had a lot of trouble with REST. I had to explain repeatedly what PUT, DELETE, GET and POST were (they weren't really familiar with HTTP at all), and that they weren't doing RPC calls."

You should try using the SQL analogy instead of RPC, as this is much closer to what a "traditional" developer might expect. With REST, one is not doing a procedure call, but one is querying to create/retrieve/update/delete data. Of course, there might be some procedures behind it, but to a client it's just a data query (just like SQL has stored procedures of its own).