When you tamed your phoenix after defeating shiro, it was a plain "Lvl 5 Pet - phoenix".
Unless you changed your phoenix' name with the "/petname birdie" command if you wished to call him "Lvl 20 Pet - Birdie" for example, you phoenix should have something before its name.
It should be either a "Lvl 20 Pet - Dire Phoenix", a "Lvl 20 Pet - Hearthy Phoenix" or an "Lvl 20 Pet - Elder Phoenix", and this is added automaticaly when leveling your pet.
If there isn't anything before "Phoenix" as in "Lvl 20 Pet - Phoenix", the only thing I can think of is that you nicknamed your phoenix "Phoenix" using the command: "/petname phoenix".
To make sure, you should enter the command: "/petname". This will reset your pet's name, and should make it appear: "Lvl 20 Pet - XXXX Phoenix", where "XXXX" is either "dire", "hearthy" or "elder".
If your pet appears as "Lvl 20 Pet - Elder Phoenix", tough luck... the HoM doesn't accept it...
What you should do in this case is go to the Zaishen menagerie and pick a lower level one to turn it into one of the other two.
Sorry for wall of text but this should cover all your questions if I managed to make sense
