The newest way to allow this was introduced in Spring '17. The original answer has been preserved for posterity below.
You cannot modify a converted lead directly. Some global actions can invisibly modify those records, such as using the replace picklist value feature and merging record types, but no normal editing method (API, UI, etc) will be able to affect those records. As stated by regal in the comment on this question, there is a pending idea that has been around almost as long as I've been using salesforce.com (and back then, I was in technical support handing out this same answer as today). The "correct" method for updating the lead would be to export the archived data, modify it, insert them as new leads, and mass convert them back into the same account/contact as previously (but it won't link to the original opportunity). Of course, this method will lose the original conversion date, although you could log that in a custom field, but it's still a hackish workaround for something that should be available at least to administrators.