Before the fall of Adam, did anything die? This seems like a simple question, but I cannot find a clear answer. The book of Genesis (1:29,30), implies that Adam just ate "plants and herbs". So I think it is safe to assume animals were not eaten? Now if animals did die, my question would be "why"?
The views of Christians on this matter can basically be divided into two.

A key passage here is Romans 5:12-21, which says:


  Therefore, just as sin entered the world through one man, and death through sin, and in this way death came to all people, because all sinned— To be sure, sin was in the world before the law was given, but sin is not charged against anyone’s account where there is no law. Nevertheless, death reigned from the time of Adam to the time of Moses, even over those who did not sin by breaking a command, as did Adam, who is a pattern of the one to come. But the gift is not like the trespass. For if the many died by the trespass of the one man, how much more did God’s grace and the gift that came by the grace of the one man, Jesus Christ, overflow to the many! Nor can the gift of God be compared with the result of one man’s sin: The judgment followed one sin and brought condemnation, but the gift followed many trespasses and brought justification. For if, by the trespass of the one man, death reigned through that one man, how much more will those who receive God’s abundant provision of grace and of the gift of righteousness reign in life through the one man, Jesus Christ! Consequently, just as one trespass resulted in condemnation for all people, so also one righteous act resulted in justification and life for all people. 19 For just as through the disobedience of the one man the many were made sinners, so also through the obedience of the one man the many will be made righteous. The law was brought in so that the trespass might increase. But where sin increased, grace increased all the more, 21 so that, just as sin reigned in death, so also grace might reign through righteousness to bring eternal life through Jesus Christ our Lord. 


Young Earth Creationists - before Adam sinned, nothing died

In the literalist view, the interpretation of the passage above is that Death is punishment for sin, and nature as subservient to mankind shares in Adam's fall. Therefore all death, even of animals, is a result of sin, and did not occur until Adam sinned.

This passage is used as one of the chief Biblical arguments that Genesis 1 should be taken literally and not metaphorically. If there were indeed millions of years of evolution before Adam, then these could not have happened without death and this passage would be contradicted.

As you already stated, Adam and Eve were vegetarians, so there was no need for there to be animal death in order for them to eat. (In fact it is not until Noah that humans are allowed to eat animals). 

Other Christians - Physical death of animals did in fact happen before the fall

If you do not hold to the Young Earth beliefs then it is clear that death of animals must have occurred before the fall. The interpretation of the Romans 5 passage is that it is about only the death of humans - death for animals is entirely natural and not the result of sin. (The NIV quoted above takes this line in its translation, but not all translations do). Some also take it to mean 'spiritual death' - i.e. that humans were always destined for a physical death, but that people would know that they were destined to pass on after death to be with God, and it would be entirely natural and nothing to be afraid of. After the fall humans would also suffer spiritual death, i.e. eternal separation from God. The Bible does elsewhere use the word 'death' to refer to spiritual death and not physical death.

If you hold that the Fall is metaphorical rather than literal then it isn't an issue.