Can nameserver issues affect SEO?

Ok, so here is what intoDNS is complaining about. I’ll first give you all the commands I executed and then explain them step by step.

lukas$ whois legacytrustuk.org | grep "Name Server:[A-Za-z0-9]"
Name Server:NS0.TELIVO.COM
Name Server:NS1.TELIVO.COM

lukas$ host -t ns legacytrustuk.org
legacytrustuk.org name server ns0.lcn.com.
legacytrustuk.org name server ns1.lcn.com.

lukas$ dig @ns0.lcn.com legacytrustuk.org NS | grep -v '^;'
legacytrustuk.org.      600     IN      NS      ns0.lcn.com.
legacytrustuk.org.      600     IN      NS      ns1.lcn.com.

lukas$ host -t ns org | head -1
org name server B0.ORG.AFILIAS-NST.org.

lukas$ dig @B0.ORG.AFILIAS-NST.org legacytrustuk.org NS | grep -v '^;'
legacytrustuk.org.      86400   IN      NS      ns0.telivo.com.
legacytrustuk.org.      86400   IN      NS      ns1.telivo.com.

lukas$ dig @NS0.TELIVO.COM legacytrustuk.org NS | grep -v '^;'
legacytrustuk.org.      600     IN      NS      ns0.lcn.com.
legacytrustuk.org.      600     IN      NS      ns1.lcn.com.

So the first thing I did was ask the Whois Server what he thinks the DNS Servers for legacytrustuk.org are. He returns the telivo.com ones.
However in the second command I ask my providers Nameservers what they think are the authoritative nameservers for legacytrustuk.org and they return the lcn.com ones
In the third command I ask your lcn.com nameserver to return the list of nameservers that he thinks are authoritative for legacytrustuk.org and he answers with the two that are present in the zone, ns0.lcn.com and ns1.lcn.com.
In the fourth command I just get some authoritative nameserver for the TLD .org and then in the fifth command query that nameserver and ask him what he thinks are the nameservers for legacytrustuk.org. He returns the telivo.com ones from the Whois info.
In the last command I ask the telivo.com nameserver what he thinks is the auth NS for legacytrustuk.org and he returns the lcn.com ones. Which by the way is the reason why your Domain can be resolved at all.

So it’s exactly as intoDNS explains. The parent Nameservers (those responsible for the TLD .org) think that ns0.telivo.com and ns1.telivo.com are authoritative for legacytrustuk.org. However when you ask them they tell you something different. And there’s the missmatch. So technically it works but formally – as far as the registar information goes – the setup is broken.

To fix this just update the Domain Registration Information. Remove the ns0.telivo.com and ns1.telivo.com nameservers from the registar info and add the two ns0.lcn.com and ns1.lcn.com servers.