A few possibilities:
You can get pain from running with new shoes regardless of whether or not the new shoes are the "best fit" for your body. Dramatic changes in shoes means dramatic changes in running gate which means you're running in a way that different than what you're used to. It's sometimes easy to overlook how a small change can effect you, but when you stretch that small change over many kilometers, it can really add up. For example, if you go from a shoe with a lot of padding to one with little padding, your body is not going to be used to the kind of impact it's about to receive. You have to train it to handle that.
Another possibility is your running store simply screwed up. They often advertise themselves as experts in running shoe technology, but really they're mostly underpaid store clerks. If you have your old shoes, you can try running in those for a week and see if there's improvements. If so, then get a brand that's similar to those. I, personally, am not a big believer in the "best fit for your foot" idea that shoe stores sell. You can run in almost any shoe, but they are all different certain ways so it requires training.
A final possibility is you're simply going to hard. It's a common mistake to attempt to run at the same intensity as one did before a break. You don't have to start at zero, but you do have to pull back a little and build back up.
The common theme among all three possibilities is you have to pull back on the distance and speed. Then build back up. It'll be a quick build-up though. Muscle memory works wonders when doing this.