I'll presume that you don't intend to use literal strings in your SQL updates; it would of course be terrible pain to change one date at a time like this.

If you have good enough access to the databases (directly or through a DBA), it would probably be good to use a real date column. Assuming MySQL, your dates can be converted with something like: update table set realdate = STR_TO_DATE(date, '%d:%m:%Y'). This will make dates like "2007-11-21". You can have you application strip the "-" signs in Perl ($date =~ y/-//d) or SQL (DATE_FORMAT(realdate,'%Y%m%d')). Later, the "realdate" column could replace the old date column.

If you can't create a new column or just don't want it, you could run the conversion internally like: update table set date = DATE_FORMAT(STR_TO_DATE(date,'%d:%m:%Y'),'%Y%m%d'). It seems a bit inefficient but it's easy to write and might be OK if your DB server is fast. The danger of going through the date functions is that the dates have to be valid (eg, not 31:02:2007) so I'd run a select (select to file if possible) before trusting an update.

For speed, leaving off any WHERE statements should help. If you still can't get this done in time, use WHERE to split the updates by year or even month-year with something like where date like '%11:2007'.

If you aren't using MySQL, the internal date format might be different but the SQL commands will probably be the same (adjusting for quoting style).