When I'm the dungeon master, I allow the Speak with Animals spell to empower the spellcaster to use Bluff, Diplomacy, or Intimidate skill to influence creatures of the Animal type. Although these creatures don't normally speak or understand language at all, the description of the spell clearly indicates that it empowers them to communicate with you and you with them. They shouldn't be able to understand complex ideas or technology, but they should be persuadable, and that means also susceptible to lying and intimidation. I also think creatures of the Animal type are too simple to lie to you and at the same time very gullible, so that unless your lie is totally absurd, they never add a circumstance bonus to Sense Motive checks.