I ran into the same problem when I first used StartSSL a few months ago.  It seemed like there were some cases where automatic verification would work and other cases where verification was deferred to a human.  I believe StartSSL is a small, possibly one man, operation, so you might have to wait a few hours for human verification.  Once my account was verified, everything after that was pretty easy and quick.