Have you tried Advance fares? I can get two people travelling Gloucester to Birmingham for £10, and Birmingham-Carlisle for as little as £25.
Overall, a very small £35 return for two people, although it may be more depending on availability. What dates are they travelling on? These tickets also restrict your parents to one particular train, so I'd allow a bit of time at Birmingham just in case anything goes wrong.