Conference paper rejected without any fault in algorithm
Since you are describing an algorithm paper, I assume you are submitting to algorithms conferences, and the "A*" description refers to the CORE ratings of CS conferences originally developed by the Australian Research Council.  The only A* conferences in algorithms are FOCS, STOC, and SODA. I've served on the program committees for all three.

These three conferences are extremely competitive, and standards for acceptance are extremely high. It is not enough for your algorithm to be correct. It is not even enough for your algorithm to offer a significant improvement on the state of the art for your specific problem. At STOC and FOCS in particular, papers are judged on their likely impact on theoretical computer science research beyond the scope of the specific result. For algorithms papers, that means either that you're describing a significant advance on a problem of central interest to the field, and/or that you are introducing new techniques that are likely to generalize to many other problems, and/or that the PC finds your result both surprising and technically impressive.

I would not expect these conferences to accept a paper that only describes a faster exponential-time algorithm for an NP-hard problem. We've seen lots of those before; yet another one is not that surprising. Unless you are proposing a strong general technique, or the specific problem you address has resisted significant progress for a long time, I would recommend aiming for a lower-tier algorithms conference: ESA, ISAAC, COCOON, WADS, LATIN, ....

All the advice in the other answers still applies when submitting to those penultimate-tier conferences, of course. It's still not enough for your algorithm to be correct. You still need to clearly explain your precise contribution and its importance to the research community. You still need to give a thorough comparison of your algorithm to the state of the art. You still need to convince the PC that they should trust you and care about your results.