My father had the same had the same problem on his work computer.
Open the terminal, go to Terminal>Window Settings
Then under the Terminal Inspector, select the Window from the pull down menu, make it any size you want to. (the default is 80 columns, by 24 rows)
Then down at the bottom press the button that says 'Use Settings as Default.'
If that doesn't work, try trashing the .plist located in ~/Library/Prefrences