I agree with Corion, store your state in an ACID database then state changes can happen in transactions. I'd choose postgresql but YMMV.

From what you've described, I don't think you'd get much advantage from a queueing system but without seeing a full & detailed spec it's difficult to tell :)