Consider a full-rank weighted least-squares problem in which the weight matrix is highly ill-conditioned. Because of the ill-conditioning, standard methods for solving least-squares problems, QR factorization and the nullspace method for example, break down. G. W. Stewart established a norm bound for such a system of equations, indicating that it may be possible to find an algorithm that gives an accurate solution. S. A. Vavasis proposed a new definition of stability that is based on this result. He also proposed the NSH algorithm for solving this least-squares problem and showed that it satisfies the new definition of stability. This paper describes a complete orthogonal decomposition algorithm to solve this problem and shows that it is also stable. This new algorithm is simpler and more efficient than the NSH method.