In my domain registrars console I see the following:
I have added my name servers to the bottom, but the domain name is not redirecting. I see there are 2 NS records above mine that I cannot change. Would anyone know if these are stuffing mine up?
If you could provide your actual domain name we could answer for sure, but from the look of the screenshot you've posted I'd say this is not setup correctly. The ns1.planetdomain.com and ns2 records are the ones being used. It looks like you've added A records for ns1 and ns2.example.com, and then NS records for ns1, ns2.example.com. I think what you meant to do was add NS records for example.com.
Typically you would change the name servers for a domain through a different interface than the one you use for adding or editing DNS records. So I'd suggest deleting the last two records shown in your screenshot, and then see if your host has a separate way of changing name servers. If not, get in touch with them.
Leave it 24 hours from when they fixed the NS issue as it can take a fair while to propagate to all name servers internet-wide.
If your still having problems then use NSLOOKUP to query it from a number of different servers. Say for example your Internode Name Servers then say the Telstra ones and maybe a root server or 2 for good measure and make sure they all agree.
It sounds a bit like there may have been 2 name servers who both thought they were authoritative for the domain with different records.