Since both of your jobs are in a bind, I would suggest looking for another job. First, approach the part-time position to see if there is a chance to get full-time work. Also, look for another job and let them know you are looking for a particular range of hours. That's a very legitimate reason to leave your current position.
You can still give it your best shot. Somehow, changing your hours is making someone else's job easier. It could be your manager or someone in HR, etc. I don't see how this could be an unexpected circustance unless no one ever took a vacation before. It's a little naive to think a company that has multiple shifts would never ask you to switch and unprofessional on their part to make such a promise. My guess is they don't want to ask someone else to make the change because this person has a history of complaining.
State your case to the person who is going to have the most trouble if you leave. Replacing employees does cost money. Let them know you were told this would not happen. The fact of the matter is you need more than one job. Maybe they have some insight on what is really going on and are in a better position to find a solution.
Is there any chance you can get over-time on this job, so you don't need the part-time job over the summer? I hate to just say find another job, but this problem may occur beyond the summer hours or repeat itself every year.