Changing name of Space in Mac OS X Lion

Not really. However if you have a space occupied by a full screen application the name of the space will change to the name of that application

Based on iconoclast's idea, you could create a sticky note for each desktop and place it in the lower left of the bottom of each desktop. it has the benefit of not requiring you to alter background images and allows you to still have a new background image every 30 minutes or so.

But I agree, this is sorely missing from Mac OS X. Linux has had this for how many years now?

The commercial TotalSpaces by binaryage allows you to name spaces. Its other features include a grid alignment of spaces and app assignments, similar to Snow Leopard.