Just a quick update:

After being on the phone with lexmark for about 30-45min, we believe that the problem is with the print head. So, they are sending me a new one and new ink cartridges. Hopefully this solves the problem.