After a few emails to M2e support, we were able to solve the problem. We had to remove the file cron.lock from the var/M2ePro folder. They said that this file is normally removed automatically and is used to prevent M2e's cron task from running more than once at certain time periods.
After removing the file, our M2e cron was running fine and updating automatically again.
Hope this helps the other people out there who have the same problem!
-Paul