Finally I found the solution. These posts helped to figure this out.
RabbitMQ on EC2 Consuming Tons of CPU
and
https://serverfault.com/questions/337982/how-do-i-restart-rabbitmq-after-switching-machines
What happened was rabbitmq was holding on to all the results that were never freed to the point it became overloaded. I cleared all the stale data in /var/lib/rabbitmq/mnesia/rabbit/, restarted rabbit and it works fine now.
My solution was to disable storing results alltogether with CELERY_IGNORE_RESULT = True in the Celery config file to assure this does not happen again.