Can't insert or delete row - not enough resource.

Hi All,

A problem that has me leaving the air fairly blue at present!

1 workbook, 2 tabs. in short its an order tracker for work.
Data Range -
Currently the columns range from A:LD and the Rows from 1:647.
There are some custom formats (basic red if over a number, green if under)
All cells from A1:LD647 have a border.
each sheet contains 15 different formulas, spread out between G5:LB23.

No data exists outside of the range A1:LD647 (that i am aware of)

The problem -

Try to insert a row - "To prevent possible loss of data, yada yada yada"
*I have followed the instruction on the screen (CTRL+END, deleting all between last cell and my data)
Try to delete 1 column within my data range of A1:LD647 -> no issue (full column)
Try to delete 1 column outside of my data range -> No issue
Try to delete 1 row either inside or outside of my data range - bang. "**Large Operation** The operation you are abou to perform... yada yada yada."
If i click cancel, the sheet hangs for about 5 seconds and then works as normal, if i click OK then the only way i can get excel to close is via task manager (unless i need to wait more than 10 minutes lol)

I have done the following:

Cleared temp folder
Cleared recycle bin
Deleted all cells (well, have tried at least) between last empty cell (via CTRL+END) but workbook crashes
Cleared contents from every cell other than my range

All with no result.

Your help would be incredibly appreciated!
galvinpaddy