Google just recently changed the functionality in Maps so that Saved Locations are now stored as part of the Web History. Previously you could save an address and label it whatever you want (i.e. Home) and then when you would start typing "H" in the search box, the saved address would show up in autocomplete. This made it very easy to search for something like "italian restaurants near H", and you just hit tab to fill in your Home address.

With the new change, autocomplete doesn't work anymore, and if you don't have Web History enabled, you can't save new locations at all! Not sure if this was an intentional way of getting more people to enable Web history or what.

There are a lot of comments about it in this thread on the help forum, and a workaround was suggested by a Google employee, but it requires Web History to be turned on.
http://www.google.com/support/forum/p/maps/thread?tid=6f662cd5481954cb&hl=en

A bit more info/better explanation can be found here:
http://www.seroundtable.com/archives/021593.html