That's an interesting question. There are a few differences between salt water and tap water. Firstly, there are dissolved sodium and chloride ions in salt water (salt is made up of these ions). There are also ions dissolved in tap water, but not as much as in salt water. Also, in a block of frozen salt water, the ions are not really part of the ice. Instead, they are trapped in little pockets outside the ice.
Due to these ions, the melting point of salt water goes down - a block of frozen salt water can melt at a lower temperature than zero degrees Celsius. This phenomenon is termed freezing point depression, and is the reason that salt prevents ice from forming when it is sprinkled on walkways when it snows. The lower melting point allows the block of frozen salt water to melt more easily than a block of frozen tap water - so it melts faster.
p.s. We have some other answers that discuss the origins of this effect and the related effect on the boiling point, e.g.:
(published on 10/31/2010)