What does the electrician that did the work have to say?

The new outlet might be on the opposite leg of your electrical service from thr old outlet. That leg might be overburdened, resulting in lower voltage on it. As Mike points out, have an electrician check. Sounds like the motor is laboring to start, which could very well be caused by an undervoltage condition, especially since it happened with 2 different machines.

The guy who did it was a maintenance guy and when I told him he said he thought it was the breaker and then he didn't show up. Called me back and said he will try to come over later this week.

Thanks for your response. Your input was very helpful. I'll contact a real electrician to fix it.

Eric