I fixed this by printing the PDF to another PDF with CutePDF Writer.
Should work with any other standard PDF writer. What this does is just convert the PDF without all the extra functions from the original PDF which was causing compatibility issues, as mentioned by Aaron McMillin in one of the other comments here.
Edit: This is a last resort fix if the above answers do not help and you do not mind striping away functionality from your PDF's. I did not need the functionality and I landed on this page so like whatevz @AlbertoMartinez.