and if that doesn't work contact Adobe support, who most certainly will help you.
I have been an Adobe customer since I purchased Photoshop 2.5 back in 1992? After installing CS6 acquired from Adobe authorized dealer back in 2013, I got similar "non Genuine" messages earlier this year. No problem for 5 years in between. I quickly found I was not alone. Numerous people with legally purchased copies received similar notifications without resolution. I suspect many just gave up and went with CC. With regards to your suggestion....."contact Adobe"....I tried that method and it nearly drove me postal.
I spent a total of 9 hours on the phone (to India) spread over multiple phone calls, never with the same person. Had to go over my problem every single time. They kept trying to push CC on me, they promised it was fixed, they promised to call back and never did etc etc....after the total of 9 hours I went on Adobe site and, in a calm but firm way, expressed my disgust of the situation and poor customer service. The post was quickly picked up by the administrator who passed it to someone "who cared". They looked into the situation and quickly resolved it......you could try a similar approach.
Happy to finally have it fixed.
My CS6 now resides in isolation from the outside world.
Registration issues, bugs and glitches happen, it's all a matter of how you are treated when trying to get it fixed. If I have a rant about Adobe....then it is their "front end" customer service, but love their software.