At lower levels bards fizzle rate seems bugged. The NPC grants 200 skill in all singing/instruments, yet despite this since the very early levels and up until now(currently level 58) my bard fizzles to the points where melody isn't an option.
With 200 in all the singing/instrument skills, I would think fizzling shouldn't be an issue until at least level 60. Definitely not on level 20ish songs(where I first recognized the issue).