I'd probably:
lslpp -Jw /usr/bin/telnet
just to make sure that telnet has been installed as part of bos.net.tcp.client.
Then I'd have a look at the version / history, and see if it has been superceded on IBM's APAR database.
Bear in mind I'm going down one route here. It could be something totally different, like incorrect permissions settings or something else.