Other monuments such as the Flavian Amphitheater use the nomen. It seems strange that the Via Appia uses the praenomen. Was this common and what political advantage did it give the Claudian gens?
The answer you're looking for is actually, and perhaps surprisingly, mundane...
...by the time the Appian Way was being built, there was already a (much older) via Claudia. That's pretty much it.