I doubt the vacuum advance would cause those symptoms. After all, many of these old engines didn't have one in the larger trucks. And at wide open throttle or under heavy load the vacuum advance doesn't work any way. Had it been in storage for a while? New fuel? Ran on old fuel?
I would pop the valve comer off and look for push rods being out of place from a valve sticking from old fuel in the past. Could be as simple as putting the push rod back in place and adjusting the valve. Make sure the offending valve is moving freely.
Sounds like this shop is a rip off artist.
