Try printing a print test sheet. If you still see the spots on the paper, it probably means your cartridges are either not the right one or aren't placed correctly.
Does your printer require you to "tell it" your replacing the ink cartridges?
Hope it helps.