I've just spoken to an advisor from O2 who was particularly helpful:
This is a copy of the email he sent me, which pertains to the Nokia N95 so make sure you set your User Agent to Nokia_N95
Setting up MMS access point
1. Press the menu button (button on the left hand side of the phone next to the Navi key).
2. Highlight 'Tools' and select (press Navi key).
3. Highlight 'Settings' and select (press Navi key).
4. Highlight 'Connection' and select (press Navi key).
5. Highlight 'Access point' and select (press Navi key).
6. Select 'Options' (left softkey)
7. Highlight 'New access point' and select (press Navi key).
8. Select 'Connection name' (press Navi key) and change to 'O2 MMS' and 'OK' (left softkey).
9. Highlight 'Data bearer' and select (press Navi key) select 'Packet data' and 'OK' (left softkey).
10. Highlight 'Access point name' and select (press Navi key), enter 'wap.o2.co.uk' and 'OK' (left softkey).
11. Highlight 'User name' and select (press Navi key), enter 'o2wap' and 'OK' (left softkey).
12. Highlight 'Prompt password' and press Navi key to change to 'No'.
13. Highlight 'Password' and select (press Navi key), enter 'password' and 'OK' (left softkey).
14. Scroll to 'Authentication' and press Navi key to change to 'Normal'.
15. Scroll to 'Homepage' and select (press Navi key), enter 'http://mmsc.mms.o2.co.uk:8002' and 'OK' (left softkey).
16. Press 'Options' (left softkey), highlight 'Advanced settings' and select (press Navi key).
17. Highlight 'Network type' and press Navi key to change to 'IPv4'.
18. Highlight 'Phone IP address' and press Navi key to change to 'Automatic'.
19. Highlight 'DNS address' and press Navi key to change to 'Automatic'.
20. Highlight 'Proxy serv. address' and select (press Navi key), enter '193.113.200.195' and 'OK' (left softkey).
21. Highlight 'Proxy port number' and select (press Navi key), enter '8080' and 'OK' (left softkey).
22. Press the right softkey 6 times to get you back to the main menu.
I've literally just got this email and posted it straight up here. I'm going to give it a crack and I'll post back the details exactly as they appear on SwirlyMMS