Okay, finally got it to work. If anyone else is still having trouble this is what I did.
Removed all the application catalogues for repository.maemo.org and r.m.o/extras except the gregale ones (as I'm running gregale).
Reinstalled Python 2.5. This time I got a different error message saying it was not successfully installed.
In xterm as root I ran:
dpkg --purge python2.5-runtime
then
apt-get install -f
I then went back to application manager and reinstalled Python 2.5 (the size of which was now showing as 1kb!) and it installed successfully.