Minor Description
Here are some things I've noted in the UnderReplicatedBlocks class that someone else should review and consider if the code is correct. If not, they are easy to fix.
remove(Block block, int priLevel) is not synchronized, and as the inner classes are not, there is a risk of race conditions there.
some of the code assumes that getPriority can return the value LEVEL, and if so does not attempt to queue the blocks. As this return value is not currently possible, those checks can be removed.
The queue gives priority to blocks whose replication count is less than a third of its expected count over those that are "normally under replicated". While this is good for ensuring that files scheduled for large replication are replicated fast, it may not be the best strategy for maintaining data integrity. For that it may be better to give whichever blocks have only two replicas priority over blocks that may, for example, already have 3 out of 10 copies in the filesystem.