Damn HTML5 specification
Some have noticed that many HTML5 sites are failing to validate recently.
As suggested here, HTML5 spec has changed recently which restricts the values in the rel attribute. So essentially any WordPress theme that uses HTML5 no longer validates because it places non-standard values in the rel attribute (noticeably rel=”category tag” appearing in the_category() function).