Restoring the iPhone did the trick. To restore the phone, you can follow the instructions in this KB article: [iOS: Unable to update or restore][1]. Afterwards, the activation worked fine.

If this doesn't fix your problem, you should check if the used SIM card is not sim and/or net locked.

  [1]: http://support.apple.com/kb/HT1808