Elk's PMS'ing. (not to be a know it all, but I've been using that LAB method for a while, too. Did try it a few years ago during my greyscale confusion, it didn't help [see below].)
Steve, your advice wasn't "faulty", IMO. Glad I could help enlighten you on that little quirk with Photoshop. There's many ways to remove color from an image in PS and they all give different results. It's hilarious. Even the Image > Adjustment > Black & White function defaults to something different from other methods. It just proves the name Photoshop is very fitting - it's for photos; full color work, etc.
Alrighty then, yes, the LAB greyscale trick is very good. Good for photos. For precise indexed art, not so much. Here's what it does to the C64 palette, which you can easily check against the REAL greyscale values below. Notes on my PS workflow to get to the result in the image. Behold:

(last step especially crucial)