"Does this sound outrageous?"
No, that is what I paid 3 years ago, and I supplied the new cam.
- Make sure they use mechanical/truck lifters.
- Make sure them to magnaflux/check the head for cracks.
- Politely ask them to be sure that all crud is out of the block, especially at the rear (all cooling system passage/journals/etc).
- If it is a car engine, get a new, truck, cam gear.
Will they paint the engine?
If yes, choose your shade of gray (they might paint it car engine blue).
