At the recommendation of someone above, I reset my icloud password (not something I enjoy doing as it was unique to itself and I have a lot of devices, but I have been meaning to change it anyway). Doing so did not instantly fix the issue, I was only able to re-log into everything but iMessage/Facetime on my recently fresh installed mac mini (10.11.4). Activation issue persisted for about 20 min, then I went to sleep. This morning I was able to log in on first try! Maybe apple fixed something last night, maybe it was the reset + waiting for an overwhelmed authentication server to catch up to the propagation.