After quite some time puzzling on the issue I decided to just fire off my problem to Twitter.
Awesome as Twitter is for these kinds of things, I had my answer very soon:
Apparently the DATE_ISO8601 is missing the ":" in the timezone offset, and the solution is very simple:
According to the PHP manual, the 'c' string also gives the ISO 8601 formatted string. However, this one is correct and working. Thanks to David Zuelke for giving me this answer, as it ensured my progress in this specific task :)