All right, maybe people already know this, but I think we've just confirmed that if they are asking for another police certificate, the one you should be getting is the first one I described that you can get at the police station instantly. We got both and sent them in just in case, but friends of ours who applied earlier than us and who also needed to get a new police check, sent in the one that takes a week... Apparently, they just got an e-mail that it's not the correct police check...
Again, this is not *official*, so you can always be ridiculously cautious (like we were~!) and send in both. Anyway, I thought I'd post this cause I wasn't able to find a very clear answer anywhere else.
Hooray for checking your criminal history so many different ways/times ; )