I don't have Photo Delux so I probably won't be much help.
Do the colours print correctly in other programs? If no, then reinstall printer software.
If it is just Photo Delux that prints wrong, then remove and reinstall that (if you haven't already).
Could it be the printer at fault?
Print on cheap copy paper till you're sure the problem has gone (the prints will be no good but at least you can test without wasting expensive paper).
I hope something here might help but if not post back with any more info you might have.