In this paper we present two new bases, B′H2 and ℬH2, for the Kauffman bracket skein module of the handlebody of genus 2 H2, KBSM(H2). We start from the well-known Przytycki-basis of KBSM(H2), BH2, and using the technique of parting we present elements in BH2 in open braid form. We define an ordering relation on an augmented set L consisting of monomials of all different “loopings” in H2, that contains the sets BH2, B′H2 and ℬH2 as proper subsets. Using the Kauffman bracket skein relation we relate BH2 to the sets B′H2 and ℬH2 via a lower triangular infinite matrix with invertible elements in the diagonal. The basis B′H2 is an intermediate step in order to reach at elements in ℬH2 that have no crossings on the level of braids, and in that sense, ℬH2 is a more natural basis of KBSM(H2). Moreover, this basis is appropriate in order to compute Kauffman bracket skein modules of closed–connected–oriented (c.c.o.) 3-manifolds M that are obtained from H2 by surgery, since isotopy moves in M are naturally described by elements in ℬH2.