As it started to look like there is no ready Java solution to do this mapping, we took the ~20 minutes to roll something of our own, at least for now.
We took the information from the horse's mouth, i.e. http://msdn.microsoft.com/en-us/goglobal/bb964664.aspx, and copy-pasted it (through Excel) into a .properties file like this:
1078 = Afrikaans - South Africa
1052 = Albanian - Albania
1118 = Amharic - Ethiopia
1025 = Arabic - Saudi Arabia
5121 = Arabic - Algeria
...
(You can download the file here if you have similar needs.)
Then there's a very simple class that reads the information from the .properties file into a map, and has a method for doing the conversion.
Map<String, String> lcidToDescription;
public String getDescription(String lcid) { ... }
And yes, this doesn't actually map to language code or Locale object (which is what I originally asked), but to Microsoft's "Language - Country/Region" description. It turned out this was sufficient for our current need.
Disclaimer: this really is a minimalistic, "dummy" way of doing it yourself in Java, and obviously keeping (and maintaining) a copy of the LCID mapping information in your own codebase is not very elegant. (On the other hand, neither would I want to include a huge library jar or do anything overly complicated just for this simple mapping.) So despite this answer, feel free to post more elegant solutions or existing libraries if you know of anything like that.