A recently proposed Chaotic-Key Based Algorithm (CKBA) has been shown to be unavoidably susceptible to chosen/known-plaintext attacks and ciphertext-only attacks. In this paper we enhance the CKBA algorithm three-fold: 1) we change the 1-D chaotic Logistic map to a piecewise linear chaotic map (PWLCM) to improve the balance property, 2) we increase the key size to 128 bits, and 3) we add two more cryptographic primitives and extend the scheme to operate on multiple rounds so that the chosen/knownplaintext attacks are no longer possible. The new cipher has much stronger security and its performance characteristics remain very good.