The Amazon queue service apparently has an undesirable use of HTTP. Seems like the design is aimed at being simple on the surface but not logical down deep.
Josh Sled provides a fairly simple Python implementation that is more RESTful. The implementation as well as the client code gets more complicated if you'd like it to be reliable, but the Amazon service provides no better guarantees.
Queues are nice. Would that they provided a tuple space.