I would remove, check and re-install the print heads (all). Make sure they are all clicked and locked into place securely (I've heard the 2500 is pretty touchy about this - make sure they are well seated).
Here is HP's article on switching the heads and troubleshooting (in case you haven't already seen it).
http://h20000.www2.hp.com/bizsupport/TechSupport/Document.jsp?objectID=bpd06188&locale=en_US&taskId=8413&taskName=troubleshoot+a+problem&prodSeriesId=25516&prodTypeId=18972&prodSeriesName=hp+2500c+printer&docId=4428
(delete any spaces in the URL).
If the issue persists and you are certain the heads are correct, it could be a problem in the print head carriage assembly. I would contact HP for assistance.