The basic configuration of the Mediant 800 is much the same as all their other gateways, the FXO port needed a little tweaking that I hadn't been able find in any other documents.
The only additional configuration that was required was under "VoIP --> GW and IP to IP --> Analog Gateway --> FXO Settings" and under "VoIP --> GW and IP to IP --> Analog Gateway --> Automatic Dialing"
FXO Settings
Change the "Dialing Mode" to One Stage
Automatic Dialling
Then we had to setup the Automatic Dialling you just need to set the phone number that corresponds to the FXO line that is being configured.
UPDATE:
So with this configuration we were seeing some issues with call quality on the Lync end. The PSTN caller could hear with no issues at all. It turns out that the Mediant with FXO ports needs to have the earth cable installed, once this was installed the call quality issues have gone.