I'm using Bitcoin Core version v0.12.1 (64-bit). When I create a new receiving address and look it up on blockchain.info it shows that transactions already exist with that address. How is this possible? Should a brand new address have zero transactions associated with it?
For example, I just created this new address "1NJXy8JSSUYjRp7V83thvUbMG1DBuKA6wc". When I look it up on blockchain.info we see two transactions.
https://blockchain.info/address/1NJXy8JSSUYjRp7V83thvUbMG1DBuKA6wc What is going on here? Has my system been compromised, or is this "normal" ?
no, it's not normal... 0.12.1 wasn't deterministic AFAIK, so it should generate new private keys at random. It should not be possible to have 1 collision, let alone multiple. If you were running 0.13.x, and generated a new wallet, it would have been deterministic (HD) if everything was left default. In that case, if your new wallet contained the same seed as somebody else's, you would create exactly the same private keys. The chances of this happening are close to 0, but still a lot larger than creating random keys and hitting existing ones each time.
Are you sure you're not using an old wallet.dat and you're seeing your own transactions? Did you already try to rescan? Are you fully synced?