This is a continuation of Part I by the authors and X. Yue [J. Algebra {\bf 263} (2003), no.~2, 228--245; MR1978648 (2004f:17021)]. Since the independent discovery around 1990 by G. Lusztig and M. Kashiwara of a canonical basis for the negative part of the quantized universal enveloping algebra of a simple Lie algebra, these bases have been computed in a few low rank cases by N. Xi. In Part I the authors and Yue studied type $A_4$, finding explicitly $62$ families of ``monomial'' canonical basis elements (in bijection with the $62$ commutation classes of reduced expressions for the longest element in the Weyl group $S_5$); these fill $62$ Lusztig ``regions'' in $\Bbb{N}^{10}$. Here they go on to describe $144$ ``polynomial'' families involving linear combinations of monomials over finite intervals. They explain their method in detail in a typical case. They also show that further polynomial elements in two or three independent variables exist, but conjecture that there are none requiring more variables. \par For background on the $A_4$ case, including a proof that the monomial elements all lie in the canonical basis in this case, see [R. Marsh, J. Algebra {\bf 204} (1998), no.~2, 711--732; MR1624436 (99j:17023); R. W. Carter\ and R. Marsh, J. Algebra {\bf 234} (2000), no.~2, 545--603; MR1800743 (2001k:17019)]. As the authors remark, recent work on cluster algebras and the dual canonical basis (by S. Fomin and A. Zelevinsky) as well as on the representation theory of the preprojective algebra of $A_4$ (by Marsh and M. Reineke) suggests that there will be $672$ regions in all. Computing the canonical basis explicitly is a very hard problem, expected to be even more difficult in type $A_n$ for $n \geq 5$ where the preprojective algebra is no longer of finite representation type [see C. Geiss, B. Leclerc\ and J. Schröer, Ann. Sci. École Norm. Sup. (4) {\bf 38} (2005), no.~2, 193--253; 2144987 ]. There may be more hope of describing the dual canonical basis due to its nice multiplicative properties. \par \{Reviewer's remark: This review is based on helpful remarks by Robert Marsh.\}