Ok, so now that we've confirmed that this is not an address collision, the question remains: What actually happened.
If you want to take the time to write up exactly what you've done with that wallet in the past 36 hours or so in detail, it might be possible to analyze your actions and make an educated guess which step led to these results.
The most likely cause would be recovering a wallet.dat backup. If you did not recover a wallet.dat backup and you are not using this same wallet.dat elsewhere, then it seems likely that there is either a small bug in the the wallet's use of the address pool, or there is a small bug in the upgrade process (if you upgraded the wallet after the first transaction and before the second).
Well there isn't much to write in details. I've done the following:
1) I've copied over my whole Bitcoin folder (it was on D:\Bitcoin , not my system drive) to a new external drive
2) I've removed the D:\ drive and renamed the external one to D:\
3) Synced up the wallet
4) Sent the 0.12 to someone last night
5) Opened it up today to sync and generate a new address
6) Made a new thread.
Just to make sure I understand you: So its a change address from a TX you did in the past (yesterday) and was now shown just recently (~1 hour ago) when you clicked "+ new" in the receiving address window?
What does "getwalletinfo" from the console return for "keypoolsize"? Bitcoin core pregenerates 100 addresses and tries to keep it that way, unless you changed this via the config file.
Yes. I didn't check the transaction that I had sent last night on blockchain.info. The address first appeared after clicking "+ new" ~1.3 hours ago
I didn't change anything via any config file.