How are you applying the choke? Are you just pulling the knob out, or are you pushing the pedal to the floor and then pulling on the knob? This can make a difference since - in stock form - the driver pushes the pedal to the floor in order to engage the choke. What this does is squirts a load of fuel into the intake (to help richen the mixture), but it also engages the fast-idle linkage which helps in initial startup and in keeping it running while still cold. Not having the fast-idle engaged (or setup correctly) would cause a lot of problems in trying to get it to start.
If that doesn't help, then maybe the fast idle hasn't been set correctly, or a part might have been left out if it didn't seem important.
Also - another thought - is if the original choke was vacuum operated, then the rebuilder might not have blocked the vacuum port to the choke housing. If there is an inverted-flare nipple on the choke housing (usually on top, pointing towards the back), then it was vacuum operated and the port might have to be plugged. Of course, the port that needs to be plugged is internal, so you will have to remove the choke housing from the carb body - the vacuum port is a small hole (about 1/16") in one of the choke mounting posts. Plug this hole with some J.B. Weld, or some lead (pieces of lead fishing weights work well) and then re-assemble the choke and you might be good to go.