The way Links used to work is that all links had a "before" and "after" bit associated with them. wp_get_links respected that, and if you had li and /li in the Links manager for those links, then that's what got output.
But Links aren't the same as they used to be anymore. So wp_get_links no longer works quite the same way. While it's not actually deprecated, it probably should be since it just ends up using the new "bookmarks" functions anyway.
I'd switch to wp_list_bookmarks to do what you need it to do.
Note that the codex is somewhat incomplete/incorrect. Hey, 2.1 is new, you know? ;)
Specifically, the "before" and "after" parameters seems to be called "category_before" and "category_after" from my look through the actual code. If you can't get before and after to work, add the "category_" in front of them. However, these default to li and /li, so you shouldn't need to set them at all.