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. 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.