You need to edit two files - both seem to be well-known and tested edits.
First, you need edit M69AP.plist and change the value for international from false to true. Once done (I think it requires a reboot of the phone) you have a new category under your settings menu - 'International'. Selected United Kingdom and this will fix the dates, so it uses day-month format.
The file is found in /System/Library/CoreServices/SpringBoard.app
You can find a better guide here:
http://hackint0sh.org/forum/showthread.php?t=10824
Second, you need to edit UIPhoneFormats.plist. If you are using 1.1.1 this is found in /System/Library/Frameworks/UIKit.framework/PhoneFormats. A more detailed guide can be found at
iPhone number format (mask) (although this was originally written for 1.0.2 so has a different directory). This is the file that needs the new 'GB' formats adding.
In both cases you'll need to convert the file from binary. I've read that you don't need to convert them back before you put them back on the phone, but I did to be on the safe side.
I have to say I still find it hard to believe that Apple did this rather than consistently using either UK or GB for the international settings, so I'd be interested to hear if it works for you.