Nevermind, Got it sorted with a little help from HoopyCat on IRC. Although I'll post the solution here for anyone looking at in future.
At the time of posting, even though BIND is capable of doing it no problem, the Linode Manager does not support this. The only way to do it is to create another zone.
1. Go to the main page of the DNS Manager and create a new zone with the 3rd level domain as the hostname. I.E. Your current setup is that you have zone with domain.tld. Create one with sub.domain.tld. Make sure you set to leave it empty.
2. Go back to your original domain.tld and add some new NS records. at the moment, you will have:
Code:
ns1.linode.com - domain.tld
ns2.linode.com - domain.tld
ns3.linode.com - domain.tld
ns4.linode.com - domain.tld
You now need to add another 4 as such:
Code:
ns1.linode.com - sub.domain.tld
ns2.linode.com - sub.domain.tld
ns3.linode.com - sub.domain.tld
ns4.linode.com - sub.domain.tld
3. After doing this go back to your newly created zone and you should be able to create an A record with * as the subdomain, making the full adress *.sub.domain.tld. This will make it point to the IP address you typed in no matter what someone puts in place of the asterisk.
Hope, this is helpful to someone at some point.
Cheers, Adam