The problem was with ds:Signature. In counter signatures you will have more than one ds:Signature entry. In my verification method I used the for loop:
for (int temp = 0; temp < nList.getLength(); temp++) {
final Node nNode = nList.item(temp);
if (nNode.getNodeType() == Node.ELEMENT_NODE) {
elem = (Element) nNode;
}
}
As you can see, there was no break when element was found so I ended up with the last ds:Signature, not the first one so all previous signatures could not be found.