Maestranzi, it's confusing for me too. First of all "majority" means that he reached his adulthood, and your great grandfather did indeed do that.
Your problems is a weird one. He couldn't legally be a citizen of both countries, but I think he certainly thought he was; and why wouldn't he since both countries accepted him as a citizen. Maybe this story will explain it.
My husband is a naturalized American citizen. One day in the 1980s he got a call from the Italian consulate in Philadelphia telling him that he was considered a criminal in Italy because he never registered for the Italian draft. My husband said, "But, I'm American," and the man replied, "Well, you never told us that, and if you ever set foot in Italy, you will be arrested." So my husband went to Philly and showed them his naturalization papers, and Italy took him off its "Most Wanted" list.
I don't think Italy ever knew your great grandfather was a naturalized American. And because they didn't know, they always considered him Italian. I think you should consider him Italian too, because that is what will work for you, but be careful that you don't submit anything to the consulate that might indicate he was naturalized before your grandfather was born.
Passenger list? What passenger list???? Forget about the passenger list and go with: "I asked for a Naturalization Certificate, and they came back with 'no records found.'"