From my own experience, I can say that this behavior seems to depend mostly on your graphics card and/or monitor, sometimes even on the video cable you use to connect both. Yeah, no joke. Once I was playing around with a SNES emulator in fullscreen mode, where I had set the resolution to 640x480. When I was using a DVI cable to connect my graphics card to my monitor, it would always stretch the image to the full screen, no matter the actual resolution, so a 4:3 screen was effectively stetched to 16:9. Once I switched to HDMI, though, the same combination of graphics card and monitor actually started accounting for the aspect ratio. So now, when I start the emulator (still with the same resolution), the aspect ratio is actually kept and I get black bars to the left and right.
One thing you might want to try: Instead of using ALLEGRO_FULLSCREEN, try using ALLEGRO_FULLSCREEN_WINDOW (or whatever it was called). That option is actually less dependent on the graphics card, so that one might be better at keeping the aspect ratio.