Does mining a block mean that anyone else who was working on mining a block loses their progress and must restart?
Yes and no.
When a new block is created, everyone on the network must discard old work and use the new information provided (assuming they don't want to create forks). It does lead to some small performance loss.
On the other hand, creating a block is more or less like playing a lottery - there is no real "progress" per se, you are just trying more and more tickets until you win something. When a new block is created you don't have a situation of "10% left, I lost so much work", as there is no telling whether there actually IS a solution to the particular configuration of a block you were creating.
All in all, yes, everyone must start over when a new block is created, but they don't lose much (aside from some small performance drop due to stale shares).
In effect, every time someone sends a new transaction to the network that the miner accepts it changes the block that the miner is trying to solve, since the new transaction gets added to the currently unsolved block and which changes the hash.
But since solving blocks is a Poisson process there is no "progress" towards finding a block and these changes don't cause miners to lose progress. Each hash you try either solves it or doesn't.
No, because there's no progress in mining blocks. If you've mined for 5 minutes and didn't find a block, you aren't any closer to finding it than when you started - the hazard function is constant.