What Keith said was correct, the clients were leaking connections which was leading to my problem. What follows is an explanation of how the leak occurred, and how I fixed it.
The whole problem was in the way I reserved messages from the queue. I used to get messages like so:
message = tube.reserve(2) rescue nil
The entire problem was the that I specified a timeout for the reserve call. Tracing the code, you'll find that method reserve in class Pool calls method send_to_rand_conn which in turn calls method call_wrap.
Within method call_wrap, if an exception was encountered, It removes the address of the connection from the list of addresses WITHOUT closing the connection, and raises an exception. And that was the entire problem.
Whenever reserve(2) was called and did not find a message in the tube, it would raise a TimedOut exception, which leads to removing the connection address. Any future call to put or reserve would establish a new connection, because the address no longer exists. Since the old connection was not closed, and a new one was being created, this led to a leakage in connections which would soon prohibit new connections from being made.
There are 3 solutions to this problem:
1) Before removing the address, make sure that the connection is closed.
2) Create a different rescue stub to handle TimedOut exceptions (I went with this option as it was far simpler)
3) Do not use reserve with timeout.
I hope I made my problem clear now, and hope that a fix for this becomes part of the official gem soon.
Cheers,