Here is an interesting blog entry about the numbers/limitations of Excel 2007. According to the author, the new limit is approximately one million rows.
It sounds like you have a workbook from before Excel 2007 opened in Excel 2007's compatibility mode (look in the title bar and see if it says compatibility mode). If so, there are 65,536 rows instead of 1,048,576 in the workbook. The workbook can be closed and opened again after being saved as an Excel workbook in the Excel 2007 format.