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 usedmake sure that your SIM card is not sim and/or net lockedneither "sim locked" nor "net locked".