Supervisor not approving submission because of coauthor he didn't approve of
To learn at submission stage who else is coauthor on a paper is unusual, indeed. So to some extent, your supervisor being annoyed is understandable. To block the submission of the paper is a rather extreme reaction though. Could there be some history between supervisor and ex-cosupervisor that you are unaware of? (e.g. your supervisor suspecting the ex-cosupervisor of data manipulation, etc.)

My suggestion would be to apologize to your supervisor for the lapse in communication, and to ask about his reason for blocking the publication. Provided that this is indeed the case, it could help pointing out that the contribution of your ex-cosupervisor happened prior to him being removed as your cosupervisor.

If this approach fails, then the right moment to speak to the vice-dean has arrived.