Maybe the maximum division count needs to be upped.

After trying to convert there should be an error message in the bottom message bar, open the script editor (shift+s) to take a closer look at the problem. There should be a sentence saying something along the lines of "can't convert, minimum poly conversion count should be set to a minimum of ######" (###### is the number we're interested in here).

Now open the convert to Sub-d options, the division count's default is something really low like 3000, change this number to something greater than the number you found in the script editor, hit convert and you should be flying.

I've not got Maya in front of me at the moment so hopefully my instructions will be clear enough for you to follow.

Take it easy,

Mat.