Okay, silly thing I was not aware of...
Facebook seems to not accepting the same Post twice in a short period of time (spam protection I guess). After I tried it again after five minutes or so, it was working like expected!
The only thing I quite don't get is why an OAuthException is being thrown...