A Restore uses the latest available software for the iPod, which may or may not be the "original factory."
If Pedometer appeared on your main iPod screen before the Restore, you had the Settings set that way. Even if it is not on you main iPod screen, you can get to it from
main iPod screen -> Extras -> Fitness -> Pedometer
If you want it on your main screen, go to
main iPod screen -> Settings -> General -> Main Menu
Select the items you want to appear on the main iPod screen from that list, so that a check appears next to the item. Pedometer is under Extras. The checked items should appear on your main iPod screen.