Go out and talk to people. Old people, young people. Female people, male people. People walking their dogs, bagging your groceries, standing behind you in line, waiting for the bus, whatever.
Start making small talk. And by that I mean small. "Gee, weird weather we've been having." or "Did you catch the game last night?"
I know it sounds dumb but this will help with shyness. When conversations don't have a lot of pressure, when they aren't fraught with meaning, they get easier. All conversations get easier, even the important ones with crush-type people.
As for her, don't sit at home and don't pine.
You're too busy saying good morning to the guy who pumped your gas or thanking the bus boy at your favorite restaurant.
PS I think her new boyfriend's a douche for making fun of you, but if you're cool with it ....