what about this straight forward approach?

while ( ($ko,$vo) = each %$old ) { 
   while ( ($kn,$vn) = each %$new ) {
     # compare
   }
}
[download]

of course there are other tricks possible like using hash slices or array slices of keys of hashes and so on...