We report Keck Observatory high-resolution echelle spectra of lithium at 670.8 nm in two of the lowest luminosity brown dwarf candidates in the Pleiades. These objects have estimated masses of 0.055-0.059 MD from their location on a color-magnitude diagram relative to theoretical isochrones. Stellar interior models predict that Li has not burned in them. However, we find no evidence of the Li line, at limits 100-1000 times below the initial abundance. This indicates that Li has in fact been depleted, presumably by nuclear processing as occurs in Pleiades stars. Interior models suggest that such large Li depletion occurs only for objects with M > 0.09 M. at the age of the Pleiades. Thus, it is unlikely that the candidates are brown dwarfs. The brown dwarf candidates present a conflict: either they have masses greater than suggested from their placement on the H-R diagram, or they do have the very low suggested masses but are nonetheless capable of destroying Li, in only 70 Myr. Until this dilemma is resolved, the photometric identification of brown dwarfs will remain difficult. Resolution may reside in higher T(eff) derived from optical and IR colors or in lower T(eff) in the interior models.