I usually leave the bottom ash door cracked on the Federal Airtight until I can hear the flames roar a little, indicating that the draft is established. Then I close it tight. You might want to try my modified approach with some small kindling and cardboard atop the paper. Big logs must remain on bottom, however, which is very convenient.
I do the same thing, but it takes more than one attempt before I can leave it be.I should mention that it always seems harder to start a fire in a stove that has no ash bed, so maybe it will get easier as we go along.