Basically, it was an UTF-8 problem after all. I found out, that I had saved an UTF-8 Byte Order Mark header to my theme's index.template.php while I had edited the file in Windows.
I use Linux on my server, so basically just I went to search for the header by looking for...
grep -R *\?php *
And looking through all the headers. And sure enough - it was there.
I removed the BOM header from the with my editor (UltraEdit) by saving the file as "UTF-8 NO BOM".
Weird how this came up only after installing TP, but I'm glad I found the cure