Note that your sprite has antialiasing. I'm not speaking of the borders (alpha on the fringe), but on the surface of the image, some pixel colors are drawn a spcific color in order to smooth the difference between pixels around it : for example a pixel can be set grey because it's between a black shape and a white shape. If such image is rotated at a similar zoom level to the original (*), the grey pixel may be preserved, and end up in a place which is not between a black and a white pixel, so it looks out of place.
This is a very simplified explanation (the rotozoom doesn't just juggle pixels), but the effect is real and can explain some oddities that appear at several angles but always at same position relative to sprite (ie. "right elbow", "corner of backpack"...)

(*) Scaling UP the sprite amplifies the problem, scaling it down makes it disappear very quickly.

For my Deluxe Pacman 2 game, I rotate the Pacman character, as the main image just faces the right. For my setup, all I really have is:

al_set_new_bitmap_flags(ALLEGRO_MAG_LINEAR);

I have a bunch of code commented out that I tried in the past, but this seems to be the one I ended up using that works well using DirectX and OpenGL.

Not sure if that would help or not, been a while since I worked on this sort of problem. And in my game the rotations are increments of 90 degrees.

Not relevant, but something you should know: the only minification filter you should ever use is some sort of mip mapping. Anything else will cause you to thrash the texture cache.