I'm not talking about rank, but whether the site shows up at all.
Page rank is the name of their search engine and is what decides whether you show up at all. Who knows why submission didn't work, they don't guarantee it on the submission page, but somewhere deep down in the bowels of Page Rank is the reason why you're not showing. It isn't related to payment though.