This report investigates design enhancements of Fiber Optic Surface Plasmon Resonance (FO-SPR) biosensors with Gold and Silver metallic films. The effect of adding a Graphene coating on the sensitivity and detection accuracy of FO-SPR biosensors is studied. We also compare the results for the addition of five layers of Graphene on both Gold-based and Silver-based FO-SPR biosensors in order to determine the optimum sensor design. Our results indicate that the sensitivity of the biosensor increases when a Graphene coating is added, while the detection accuracy decreases. Results also demonstrate that the sensitivity due to adding Graphene sheets increases more for Silver-based biosensor when compared to Gold-based biosensors.