Serial Port already in Use

I thought that max/msp and arduino have to be on the same port to be able to communicate?

They do. Your issue appears to involve bluetooth. That's a horse of a different color. Get rid of the bluetooth crap, and see if the problem goes away.