You probably don't have enough friendship. Source.
According to Serebii, to get the Footprint Ribbon you Show Mr. Footprint a Pokémon that has gained 30 Levels or has high friendship. According to Bulbapedia, Dr. Footstep will say the following when you have Max Friendship with your Gastrodon:
Level 5: "That is the most impressive of humans. It takes a lot to make me, , sunny and cheerful! As a show of affection, I should chomp down on the Trainer's neck... Hahaha... Have no fear... I was merely joking..."
If it says this and you still don't get the ribbon, please let me know! if not, you likely don't have max friendship.
Here are some ways to increase Friendship in BSDP:
- Do not let the Pokémon faint (decreases friendship).
- Feed the Pokémon vitamin items like Zinc and Iron.
- Feed them certain berries that say "raise friendliness."
- Give the Pokémon a massage in Veilstone City.
- Give the Pokémon the Soothe Bell Item. This item will increase friendship faster.
- Use items on the Pokémon.
- Win battles with the Pokémon.