The input does not look valid to me (Mark O'Connor says it's valid, but I don't see any argument to that effect, just a bald statement). Equally to the point, it doesn't look valid to Xerces J or to Saxon EE.
The XSD support in xmllint is known to be a bit spotty, but mostly that means that there are parts of the spec that aren't supported; this looks more like a straightforward bug in the regex routine. I see several unresolved regex bugs in the gnome bugtracker for libxml; perhaps this is related. I've opened a new bug report with this issue.