Hey VR4, it sounds to me like what you have on your hands is not grease and grime, but the black oxide coating. This is a very common if not universal experience with BO Leathermans.
Take a paper towel or two and rub every surface pretty vigorously. That will remove that loose (my terminology), papery outer layer of the BO, and after that it will not get your hands dirty.
Rub a paper towel on it, and look at the paper towel. You'll see what I mean.
Peace out.