Because of messages I received about the mail server being insecure, I was told to change my password. This I did with relative ease, got a "verification code" to use, went through two or three steps to verify this and thought all was well. However, when I try to log into my Gmail, it asks for my user name and password. Neither the new nor old credentials work. What do I do now?
It sounds very likely you got hit by a phishing attack that enabled someone else to take control over your account. Unfortunately, short of contacting Google support, you likely have no meaningful recourse.