Paul:
Cheapest solution:
If your go to a digital printer they will be ablt to do this - BUT the reds will be muddy and not bright.
Expensive Solution:
Go to screen printers - set up cost is expensive but they will get the colours spot on, and the result will be 100% better. Expect to fork out £100/£150 plus for a two colour job.