I had the same problems with SQS and ended up using RabbitMQ and haven't had any problems. The main issue I saw with SQS was a couple seconds on unavailability every couple of days, enough that I had to start writing lots of client code to deal with it. RabbitMQ is rock solid.
