I was told that it was done just before I got the car from the previous owner, but I suppose it wouldn't hurt to change it. Also, an update, I read on some other forums and threads that someone was having a similar problem and checked out their fuel pump relay, so I pulled mine, gave it a few taps and put it back in. I was able to start the car over and over. I'm thinking I may just have a dirty/bad relay. I would still appreciate extra input though. Thanks.
1995 BMW 325i Automatic 168,000mi