In my first job out of school I was so shy around my boss (who was one of those never give any feedback positive or negative types) that I made an idiot of myself every time I saw him by falling off my desk chair, running into the wall, etc. So I know how you feel. I could not look anyone in the face for years due to shyness and other issues that I prefer not to discuss. This impacted my early career negatively until I got a boss who flat out told me I had to improve or I would stay junior my whole life. He believed that I was smart and capable but at work you need to be more than that. You need to be able to deal effectively with other people. And you need to believe in yourself.
The solution is in you. You say that you are shy, fine, learn how not to be shy. Being shy is an excuse. It is limiting your life. You have to learn to be assertive to succeed whether it is easy for you or not. It certainly wasn't easy for me and it took years to accomplish. I am a natural introvert, but my current coworkers would not suspect that now. I am sure they would not recognize that timid girl who ran into walls trying to avoid her boss.
Now the hard part is how to do that. There are classes on assertiveness training. There are organizations like Toastmasters that help you learn to speak publicly (and once you can address a group, talking to individuals becomes much easier for the most part.) There are books on assertiveness training and books on how to use language more effectively (http://www.amazon.com/The-Gentle-Art-Verbal-Self-Defense/dp/0880290307/ref=sr_1_1?ie=UTF8&qid=1406917413&sr=8-1&keywords=suzette+elgin+hayden). Read them. Practice the techniques they teach.
Make goals for yourself. Write out and memorize a script for talking to the lady in the elevator. Practice it until you feel comfortable with it and then one day when you are ready, say "Hello, Jane. How is the XYZ department doing today?" or whatever your script says. What is the worst that can happen? Is it worse than running into the wall like I used to do?
The more you make specific goals to talk to people and the more you actually accomplish the goals, the more confortable you will get doing it. Start small. Have a goal that you will smile and say hello to 2 people in the hallway. When you have a meeting planned, write out one point you want to make in the meeting and then make it. Work up to the lady in the elevator if you must.
Video tape yourself pretending to speak up at a meeting or give a work presentation. Spend a whole day at this. Videotape, review the tape to decide what to change, try again with the thing you decided to change and video again and keep this up until whatever you are doing starts to feel more comfortable. Exaggerate in the opposite direction (this works in learning just about any new skill). If you talk too softly, resolve to shout in one of your practices (it is likely to come out at the right volume then!) If you hold yourself in a tight box, practice making overly expansive gestures. Because it is just you and the camera, no one else will see what you do and how silly it looks when you exaggerate, but the exaggeration will help you relax and move and speak more normally rather than timidly in the next practice run. It is hard, hard, hard to watch these tapes (trust me I know!), but after you start to see improvements you will realize how much it helps. Dedicate a whole weekend to it if you can. Or do short sessions for several weekends in a row. Do not expect it to get better instntly.
Pick someone else who communicates well and pretend to be that person when you decide how to respond to something. This is acting but acting skills are handy in teaching you the skills you didn't learn becasue you were "shy", Once you master them, you can much more easily learn to relax in communicating with people. Acting classes or trying out for the local theater group can help too.
And remember there are many more ways to communicate at work than through in-person conversations. You need to up your game on email and IM or whateever other forms your office uses to keep people in touch. Perhaps the complaint of not communicating enough means you don't tell people when there are delays or you don't answer questions in emails soon enough or you don't talk up in meetings. These things are all probably more important than talking to people in elevators. Think about what you can do to communicate more effectively in all modes of communication.
One thing that can help tremendously is to find a behavoral Psychologist. This person will give you technicques to help you learn to interact more with other people. It can be difficult to get started and having someone who gives you specific things to do and then expects you to report on your progress in doing them can be helpful.
Remember being shy is an excuse. It is just an obstacle to overcome; it is not a wall preventing action. Sure it makes it more difficult to learn to communicate well, it doesn't make it impossible.
You can do this. It is hard work but it is possible. Believe in yourself. You can do this.