I don't know much about colour laser printers, but I'd first look at the type of toner it uses. Thats why HP might be a good idea (even though they are usually overpriced).
I bought HP4L about 13 years ago, but can still easily find new or refilled toner for it.
Of course, price per printed page is very important.
