I sent my host an e-mail explaining the situation, and it turned out that all I had to do was CHMOD the wordpress-folder to 755. Simple, really, though I still have no idea why it used to work but then suddenly didn’t.
I have the exact same problem, and it really annoys me.. Don’t even know how it appeared, it just suddenly stopped working.
johnoz: I can replicate it. Write + save + publish = Published, but with error message. Write + publish = Success.
Sorry for not answering sooner, my blog kinda temporarily died because I’ve been busy.
Edit: Info, if needed.. The domain in question is http://tykjpelk.net. PHP info from the host: http://www.dcvhost.no/phpinfo.php (not sure if it’s relevant or not)