I love these "Help me name my business" kind of questions on HN. It allows me to go a little crazy with my creativity. Anyway, here are my ideas.

First, the serious ones (stupid ones to follow)

Parts Smart

Parts Mart

Car Gutz

Purr-fect Auto Parts

The Autocrat (or The Auto-Crat)

The Auto-Dialler

The Auto Loader

Now, as promised, the ridiculous ones (the ol' reverse-psychology trick of telling your customers you're serious by giving yourself an un-serious name)

Mister Smarty-Parts

Major Partz

Underhoods

Captain Sparky

The Great Crate

Heap o' Fixin's

Drivin' Monkey, The Car Parts Junkie

I Heart Parts

Mister Friendly's Autocracy

Sloppy Jalopies