It's tough to give definitive advice without seeing a screen shot of the footage.
But given the way you describe it, here's one good piece of advice: reshoot with a proper exposure. If you need to darken the footage for a certain look, AE has many tools available, which can be used in conjunction with your own lighting enhancements for something like day-for-night shots, for example.
Motion track or camera track? There's a huge difference. If the footage is really bad I'd duplicate the layer and enhance the details as much as you can, then pre-compose that copy and motion track or camera track the pre-comp. Then just use the original footage in the project.
If it is motion tracking then pick bigger areas that have detail. This depends on what you are trying to track. Like Dave said, it's nearly impossible to tell what the best technique is without seeing the shot. Mocha might even be your best option.
Thank you both very much!!!!!!!!!!!