Many moons ago when I used to use Excel 2003 I often had a slow cut/copy/paste experience if the spreadsheet was set in page break view but not if in normal view.

If that's not the case for you and you're experiencing this problem with a new blank workbook then I'm not sure what to suggest other than a fresh install or an upgrade.

I'm sure someone will be along with a more helpful solution for you.
Sorry I can't be of more help.