Changing your stem and bars will probably help you- a LOT. Don't give up yet! Let the second LBS help you and work with you. Also keep in mind that the first few rides in a drastically new position (road vs. hybrid) will leave you sore.
You might want to try "albatross" bars, and not only a higher stem but a shorter stem. If your hands are at the same level as your seat (instead of lower) you will be more comfortable.