What does it mean if my advisor decides to remove his name from a paper we co-authored?

Please ask your advisor politely. There can be numerous reasons he wanted to have his name removed:

• The quality of your work is too bad and the paper might affect his reputation. I do not believe that this is the case. You worked together on the paper for the first submission where he agreed to be on author list. Why should he remove his name when there is better content, now?
• No right of authorship: He may know that all of the work was done by you and he has too little contribution to the paper. So he is friendly by declining authorship of your work. This might be quite likely, at least this has happened for me. However, if this is the case, consider including him in the acknowledgements.
• He wants you to become more independent. You may have worked rather closely on the first paper but now he wants you to take the lead and do most work on your own. This may be due to a limit of time on his side.

All in all, just ask him, you need this answer/feedback to continue your work.

Yes, you should definitely ask him about the reason he decide to remove his name from the paper. Also I don't think it will be a huge impact on you or your paper if he still decides to get his name removed.