I'm In the same boat as you. I bought my first horse four weeks ago and, being an anxious novice, I was a wreck. She did have some issues crop up after the move that she didn't have when I tried her. I rode her every single day for the past month under instruction of my trainer and I took her for long in-hand walks. Most of the lessons consisted of me on a lunge line, mostly walking in circles and some nervous trotting. My trainer rode her a bit in every lesson as well.
A couple of days ago, I had a very bad lesson, I felt nauseous and I had to get off 10 minutes into it, that's how scared I was - even though the initial issues have been solved and she didn't do anything wrong in a while. Then, suddenly, the very next day my anxiety disappeared. I have no idea what happened, but I took two lessons, all trotting and a tiny canter, without the lunge line AND I went on walk, riding this time, on a trail on my own. I have to say, seeing a 10 year old girl whom my trainer had ride her without problems also helped.
I have to say that there seems to be some sort of a bond forming. She looks to me when unsure, walks up to me as soon as she sees me in pasture so that I can save her from the meany gelding (he doesn't do much, just glares)... She also recognizes my trainer and she will gravitate to her in school if I'm not giving direction. It's quite funny, today I put her between the door and my trainer to check which has the stronger pull, she bobbed her head up and down because she couldn't make up her mind.
Best of luck