I almost hate to have to post this, but...
...did you remove the tape from the ink cartridges before installing them?
Laugh if you will, but I actually had a help desk work order for an issue like this, and I walked in, took the tape off the cartridges, put 'em back in, and walked out.
When I...