Ok, for some still unkown reason I got it working. I looked into the source code of the wp-admin/themes.php?page=custom-headerpage and noticed the following on line 195:
<input type="hidden" name="_wp_http_referer" value="/wp-admin/themes.php?page=custom-header?page=custom-header" />
It says ?page=custom-header?page=custom-header twice. And when clicking the Save Changes button I noticed it added &step=1 to the end of the URL. So, I decided to manually edit the URL to end like this: wp-admin/themes.php?page=custom-header&step=1
And for some reason everything suddenly works. I still don’t know what the problem was and why it suddenly works now, so I think there’s still something that needs to be fixed to prevent this from happening.
Ideas anyone?