Взаимосвязь самая простая: эти названия придуманы не живущими там народами, а европейскими колонистами. Изначально слово "Гвинея" заимствовано португальцами у берберов, у которых оно обозначало "обгоревшие люди" и использовалось для обозначения всех негров. Потом из названия людей оно стало названия западного побережья Африки южнее Сахары, так что все нынешние африканские Гвинеи - это осколки огромной португальской Гвинеи.
А когда испанцы доплыли до Папуа, они решили, что местные аборигены внешне очень похожи на африканских гвинейцев и не долго думая назвали свежеоткрытый остров "Новая Гвинея".