Couple of ways. One is to go into your 'App settings' tab then 'regional' subtab and change the way your locale shows dates. That'll change all dates used throughout your blog. To see the codes that change the date format pretend you want to create a new locale and you'll get the full list. So for example it looks like your locale is one that uses "m/d/y" for the date fmt. Change it to "l, jS F, Y".

To change a specific place where the date shows up (instead of all instances) you need to open skins/yourskin/_main.php and find the function that is making the date show up, then include the little code above in that function call. For example

$MainList->date_if_changed();

would become

$MainList->date_if_changed( 'l, jS F, Y' );

* I'm pretty sure that's how to put it in the function call, but it is untested so technically speaking I'm just guessing.

Success! Changing the code in _main.php didn't work as it only published the letters inserted along with the date as before.

HOWEVER, the change to the region worked but then - see the edit below:

Oops. Seems changing the regional date format to "Monday, 23 October 2006" makes that the default format for entry into each post's date published field and it won't fit. Manually changing the field back for each post doesn't work as b2e doesn't recognize the old format any longer. Grrr. Guess it's back to the drawing board...