I'm curious what problems you guys are running into. Redis has been one of the best and most reliable pieces of software I've ever used.
I have full faith in Redis as a tool, and I'm sure there are reliable queue/worker libraries that work with it but we don 't have one of them. even with a reliable datastore you need to make sure you're not dequeueing things twice or putting things back on the queue or suddenly having your workers stop processing things - we've seen all of these, and like everything, it's been tricky to balance "rewrite the entire thing" vs. "make it good enough & focus on delivering business value".
Interesting about your Redis issue. I've found it to be reliable. Could you email me? (check profile) I'll try to help troubleshooting. The job sounds interesting, but troubleshooting is more fun. :)