I've ran into this bug, and crushed it. 
The problem is in the PolySelectTraverse script and the polyListComponentConversion command. It looks like they are using the polyListComponentConversion (pLCC) command to determine the selected component type. For some reason, pLCC will start to output vertices even tho faces, edges, or uvs are selected. So if you change the PolySelectTraverse script to use filterExpand instead (pLCC is a very strange choice anyway) it will work consistently. Here is my version of PolySelectTraverse:
global proc PolySelectTraverse(int $traversal)
{
string $result[];
// Vertex first
$result = filterExpand -sm 31;
if (size($result) > 0)
{
polySelectConstraint -pp $traversal -t 0x0001;
}
else {
// Then edges
$result = filterExpand -sm 32;
if (size($result) > 0)
{
polySelectConstraint -pp $traversal -t 0x8000;
}
else
{
// Then faces
$result = filterExpand -sm 34;
if (size($result) > 0)
{
polySelectConstraint -pp $traversal -t 0x0008;
}
else
{
// Then uvs
$result = filterExpand -sm 35;
if (size($result) > 0)
polySelectConstraint -pp $traversal -t 0x0010;
}
}
}
}
However, this does not address the issue of why PolyListTraverse is inconsistent.
Also, I'd recommend backing up PolyListTraverse in case this breaks something else.