There are some neat exercises to help overcome fear of stalls. Try these:
Hold the stick all the way back so that the airplane stays in the stall, power off. Don't move the ailerons--keep the yoke straight. Control the airplane's tendency to fall one way or the other with the rudder. Some call that a falling leaf stall, others call it walking the rudder. Not only does this help with fear of stalls, but it also develops more understanding of what the rudder can do.
Hold the stick all the way back so that the airplane stays in the stall, power off. But instead of catching the falling off tendency only with rudder, prevent it completely with both rudder and aileron, so that the wings remain level at all times. Now watch what the airplane does. The nose will drop after the stall, and then the airplane will start flying again, on its own. But as you keep the stick all the way back, it will stall again, and then the nose will drop again--same thing over and over. It's called a phugoid. It not only helps with fear of stalls, but it proves that the airplane really wants to fly and not fall out of the air.
One of my close friends, Kenny, was pretty far along in his private training while I was working on my commercial, way back when. Kenny was deathly afraid of stalls. Our mutual instructor, George, asked me to take Kenny out and show him both of these techniques, I guess on the theory that if low time Cary can do them, Kenny can do them, rather than the experienced, ex-Marine fighter pilot ATP CFII George showing him. So Kenny and I went out for an hour or so, and we did them, first me, then Kenny, back and forth. That was my first "instructor gig". Anyhow, when we were all done, Kenny was no longer afraid of stalls. Later on, when I was really an instructor, I used those same techniques with my students, although truth be told, I never had a student so afraid of stalls as Kenny had been.
A large part of any instructor's duties to his/her students is to help them to overcome the fear of the unknown. That's why you spend time learning the rudiments of aerodynamics, and why you're shown different maneuvers before you try them yourself. We all grow up in a 2-dimensional world, and working in 3 dimensions is pretty strange to us at first. The whole idea that an assembly of aluminum weighing around a ton can levitate, although we can conceptually accept it, is pretty marvelous and hard for our minds to really get around it. That it won't fall out of the sky if we do something too quickly or not exactly right is just as hard for our minds to get around. I can't tell you how many people I've taken for rides who are absolutely afraid to touch the control yoke, or if they do, they treat it like it'll vaporize in their hands.
So have your instructor show you the falling leaf and phugoid stall exercises, and practice those a little, and I'll bet that your fear of stalls will subside significantly.
Cary