I must say I'm surprised the shop didn't use the Red Box. It's basically a device that can recognise contacts on a wide variety of devices and extract them. They're not stored in an easily accessible place or format, so special software is always required.
When you have everything you can get, make sure they're all stored as Google contacts. Ask the store to give you a comma-separated or vCard file and import that into Google. That way, next time you change phones, they'll come back by themselves as soon as you sign in.
As a belt & braces, you can export to vCard in the phone's Contact app (it's usually a sub-option of Manage Contacts). Upload this file to cloud storage (ideally not the same service that syncs them) or email it to yourself and store it somewhere else as well, such as a pc - in fact, the more places the better!
