I encountered the exact same issue and managed to solve it. In my case, the previous answers did not work (though I can affirm they do work in other cases). Here is the cause, diagnosis, fix and prevention in my case, which might be the same as in yours:
CAUSE: If you formatted tour data as a table, it is possible to (accidentally) have formatted the data as TWO SEPERATE tables (or more) side by side. If this is the case, you can no longer insert or delete rows (because it would affect two tables at the same time), while you can insert or delete columns (affecting only one table).
DIAGNOSIS: The way find out if this is the case: go to 'Table Design', select 'Resize table'. Check if either the first column of the array is not the actual first column of your intended table, or if the last column is not the actual last column of your intended table. If this is the case, you have accidentally created multiple tables next to each other.
FIX: Select a cell in each of the tables and for all of them click 'Convert to range'. This will undo the definition of your data as tables. After that, select any cell in the range you want to convert to a table and on the home button click 'Format as table'. This time, make sure all your data is in its range.
PREVENTION: Whenever you add a column to the left or right of your table, make sure you adjust the range of the table correctly. To the right and in the middle of a table this usually works automatically, to the left I think not or not always. In any case clicking 'Resize table' and selecting the correct range will prevent things form going pear-shaped.
Since @Pproteus did not mention a message saying "can't insert new cells because it would push non-empty cells off the end of the worksheet" and because he says he can add columns, I think chances are he had the same problem as I described above. In that case, removing the bottom rows will not work. I feel silly for creating this problem, but wanted to share my relief in fixing it. Especially since so may of you have unknowingly helped me so many times by sharing your problems and fixes. Thank you for that!