Googling for this error message turns up a boatload of different possible reasons, mostly related to missing device entries in /dev/

The traditional simple explanation would be that you are simply running out of ptys; there's a kernel compile-time limit you can set but it should be reasonably high. Do you have a large amount of concurrent logins?