You can't re-label the actual column headings. The only way you can change the A, B, C... is to go into the Tools Menu, select Options, click on the General Tab at the top, then put a tick into the box named R1C1 Reference Style. But this'll only change the A, B, C... to 1, 2, 3...
And I guess this isn't what you want to do.
As others have said, you can't do it in Starter, see this link from Microsoft:
http://office.microsoft.com/en-gb/starter-help/excel-features-that-are-not-fully-supported-in-excel-starter-HA010374501.aspx
But wouldn't you be safe to install the version of Office you have on your desktop onto your laptop? Do you still have the disks?