Don't use max(). Instead, calculate the length of the diagonal of your sprite and use that. Otherwise you might clip the corners off depending on the shape of the sprite!
Then one method you can do is to pre-draw a set of rotations to a bunch of bitmaps, then all you do is choose which of those frames to draw mid-game. Sure, it doesn't look as smooth as doing the rotations on the fly, but to really get alpha-blended plus rotated quality you should be doing hardware acceleration, either yourself or with Openlayer or AllegroGL.
You also must be using 32-bit colour bitmaps. Allegro doesn't support alpha channels in any other colour depth. (However, you might still be able to get away with drawing a 32-bit alpha-blended sprite onto a 15/16/24-bit surface. Just make sure to disable colour conversions when you load the sprites you plan to draw in this fashion, otherwise they will be converted automatically to be 100% compatable with the current screen format, and thus might lose their alpha channel.)
--- Kris Asick (Gemini)