The current law does suggest so. The law does not actually contrast "nationality" and "citizenship" as the translation suggests: it says that the grandparent "não tenha perdido essa nacionalidade" (has not his his/her nationality). The part that would remain to be determined is whether both grandparents lost their Portuguese nationality somehow. The most likely reason for that would be renouncing Portuguese citizenship, for example to take US citizenship. That matter could probably be resolved by researching the law of Portugal and the US at the time the grandparents became US citizens (if they did). Both countries currently allow dual citizenship and as far as I know the US has never required a person to formally renounce their other citizenship to be naturalized. The verbiage in the current US naturalization oath that resembles a renunciation of citizenship:
I hereby declare, on oath, that I absolutely and entirely renounce and
abjure all allegiance and fidelity to any foreign prince, potentate,
state, or sovereignty, of whom or which I have heretofore been a
subject or citizen...
might suffice. Loss of nationality under Portuguese law simply says
Perdem a nacionalidade portuguesa os que, sendo nacionais de outro
Estado, declarem que não querem ser portugueses. ("Those who,
being nationals of another state, declare that they do not want to be
Portuguese lose Portuguese nationality")
Some other countries make it much more difficult to renounce citizenship. One would need a Portuguese con-law attorney to know whether this legally means that you must first become a national of another state, and then declare that you don't want to be Portugese (or, can the renunciation precede the moment of naturalization?). (The fact of coming from Madeira is not significant since Madeira is still part of Portugal, whereas coming from Mozambigue would be). The main practical questions is, what were the laws at the relevant time?