Absolutely. A fixed reward (25 BTC) is rewarded each time a block is mined. Each block is based on the prior blocks in the chain, so when one miner mines a block, all the other miners must start over. Blocks are mined on average once every ten minutes, so basically, a random miner is selected approximately once every ten minutes to receive a reward.
Saying they have to start over is implying that you're somehow making progress. The only progress your are making is just ruling out a few inputs from a massive search space. You don't really lose any work when it resets because the work you've done is useless.