We present Bayesian Analysis for Nearby Young AssociatioNs II (BANYAN II), a modified Bayesian analysis for assessing the membership of later-than-M5 objects to any of several Nearby Young Associations (NYAs). In addition to using kinematic information (from sky position and proper motion), this analysis exploits 2MASS-WISE color-magnitude diagrams in which old and young objects follow distinct sequences. As an improvement over our earlier work, the spatial and kinematic distributions for each association are now modelled as ellipsoids whose axes need not be aligned with the Galactic coordinate axes, and we use prior probabilities matching the expected populations of the NYAs considered versus field stars. We present an extensive contamination analysis to characterize the performance of our new method. We find that Bayesian probabilities are generally representative of contamination rates, except when a parallax measurement is considered. In this case contamination rates become significantly smaller and hence Bayesian probabilities for NYA memberships are pessimistic. We apply this new algorithm to a sample of 158 objects from the literature that are either known to display spectroscopic signs of youth or have unusually red near-infrared colors for their spectral type. Based on our analysis, we identify 25 objects as new highly probable candidates to NYAs, including a new M7.5 bona fide member to Tucana-Horologium, making it the latest-type member. In addition, we reveal that a known L2{γ} dwarf is co-moving with a bright M5 dwarf, and we show for the first time that two of the currently known ultra red L dwarfs are strong candidates to the AB Doradus moving group. Several objects identified here as highly probable members to NYAs could be free-floating planetary-mass objects if their membership is confirmed. ; Comment: 35 pages, 10 figures; accepted for publication in The Astrophysical Journal (in press); Several typographic corrections