I too was having trouble getting my first couple C02 bottles to start until I read and followed the following procedure:
Mix the yeast in 1/4 cup water at temp of 104 degrees (instructions actually said between something like 90 and 110 but identified 104 as the best temp)
Stir rapidly to make bubbles which dissolves oxygen into the mix.
Add small pinch of sugar, stir again. Wait approx 10 minutes. I usually wait until the 1/4 cup I started with has doubled to 1/2 cup.
I add 1/2 the amount of (hot) water to the bottle. Dissolve the sugar, add the rest of the water (cold).
Add yeast mixture and shake the bottle.
I have mixed around 10 bottles using this method and have C02 within 30 minutes on every one of them.
However, I do use more yeast than many recipes recommend. I have 2 bottles set-up and change one approx every 7 days. Keeps a nice steady flow. I have 2-3 bps consistent.
2 cups sugar
No baking soda
1 tsp Yeast
bottle filled to the bottom of the curve of the pop bottle