Daniel in Ottawa has a lot of trouble getting the fire started without smoke in the house.
Chimneys on the outside of the house always have more problems than chimneys that run up inside the warm part of the house. There may not be enough air available for the draft to start, which can be demonstrated if simply opening a window while lighting the fire solves the problem. In fact the whole operation of a wood burning fireplace in the era of our tightly sealed houses gets complicated. Follow this link for detailed information about wood appliance chimneys.
A little help for a marginal problem can be had with a draft assist cap that turns in the wind to assure that the wind is working with you and not against you. I know of two Canadian companies who supply chimney top draft assists or "wind directed rotating caps": Aim Chimney Sweeps in Penetang, Ontario and Industrial Supplies Ltd in Rougemount, Quebec.
Exhaust fans in the house can also affect the draft up a chimney. Check out "Spillage Susceptible" in the keywords search.