To be grammatically correct, "…, the first step is…" needs to be followed by either an adverbial phrase ("The first step is really hard") or a noun phrase ("The first step is the hardest step").
To turn the verb phrase "change your mind" into a noun phrase, you need to use either a gerund ("…, the first step is changing your mind.") or the to-infinitive ("…, the first step is to change your mind.").
Hence, it the first of your two sentences is incorrect, the second correct.
Edit: Actually, there is a second option. We could split the first one, and turn "change your mind" into a imperative statement:
To eliminate your problems, the first step is: change your mind!
Then it becomes a build-up, followed by a command as a separate clause.