Hi Ben,
1) Click one of the symbols you want to replace, then go to Select>Same>Symbol Instance. This will take care of selecting all the matching symbols.
2) Now go to the symbol palette and select the new symbol that you want to replace the old one with and then click on the dropdown menu at the top right of the symbol palette (down triangle with horizonatal lines icon) and select "Replace Symbol"
That should do it!
Cheers,
Adrian