Лучше использовать обход в обратном порядке
<script type="text/javascript">
function ulsdel(){
var UlList=document.getElementById('uls').getElementsByTagName('ul');
for(i=UlList.length; i--;){
UlList[i].parentNode.removeChild(UlList[i])}
}
</script>
<div id="uls">
<ul><li>первый</li><li>первый</li><li>первый</li><li>первый</li></ul>
<ul><li>второй</li><li>второй</li><li>второй</li><li>второй</li></ul>
</div>
<input type="button" onclick="ulsdel()" value="Удалить UL">