Thanks for getting back to me!
This is really starting to not make any sense to me.
I have done what you suggested, but in order to delete the accounts, I had to use the Core Control WordPress plugin to disable the cURL Transport within "External HTTP Access". With that disabled, I was able to remove both the Twitter account, and the Facebook account.
I then added the Twitter account back in, and still with the cURL Transport disabled, I did a test blog post, and publicize successfully post to Twitter.
However, when I re-enable the cURL transport, doing another test blog post means that Publicize no longer works.
The really confusing part is that I have another blog, http://www.gep13.co.uk/blog, which is hosted on the same server, with the same plugins, and Publicize works perfectly there, without the need to touch the cURL transport. On this blog, it is enabled.
Can you think of any reason my Publicize works in one place, and not in another?