Every type of Shaman specifically lists which domains are valid choices for Nature Bond. For example,
the wolf shaman must choose from the Animal, Community, Liberation, and Travel domains.
None of the Animal and Terrain domains are listed here, and the list was never updated to incorporate them since Ultimate Magic came out.
Without any special rulings by Mike Brock regarding PFS, the combination is not therefore not PFS legal.
As a Houserule: Highly sensible
Of course, as always in a home game, the GM should be open to houseruling this, especially given the silliness of a Wolf Shaman being unable to take Wolf Domain.
The Terrain domains are not as clear though. If it were me, I'd allow for domains associated with the animal in question (or a subtype of that animal), such as Plains for the Lion Shaman, or, barring corresponding character fluff, the Arctic domain for the Bear or Wolf Shaman.
But you shouldn't be surprised if you are denied your choice of domain by some GMs. No matter how much sense it makes, these are houserules.