Be warned, GIMP 2.8.2 is producing invalid bitmaps that won't load in A4. No matter whether I go 32-bit, 24-bit, or 16-bit, none of them will load. However, using say, MS Paint works just fine. If I produce an image in MS Paint, and then load and export the same image from GIMP? No dice.
I've looked online and plenty of other people have shown the same problem dating all the way back to 2008. I've also seen some forum posts on Allegro that describe the same problem I'm having.
What a pathetic, glaring issue to leave wide open (on GIMP's part). 
Are you talking about Windows .BMP format? Does MS Paint load the Gimp images? If so, I'd have to say it's Allegro's fault.
Well, that is possible that it is Allegro's fault.
MS Paint does load the "bad" GIMP bitmaps, but once MS Paint saves the exact picture, they are definitely different in structure and size. (see attached.)
It appears that the GIMP version adds additional data to the header section. Perhaps it's in a different "bitmap version header" (1/2/3/4/5), but from a brief read, I think longest headers are supposed to be the later versions. Under a hex editor, it appears to add a section with a start denoted by the letters "BGRs."
Also, while the ones I posted are both 24-bit; in my program, I tried 32-bit /w alpha, 32-bit /w padding, 24-bit, and 16-bit exports and none of them would load under Allegro.
Made a little search using a hex editor, these use the BITMAPV4HEADER, Compression method is zero (ie. raw 24bit RGB data). Height is positive, so it doesn't use the bottom-to-top encoding. So far it seems to be very classic.
Grafx2 loads them fine, and its BMP-loading function is here (Load_BMP) :
http://grafx2.googlecode.com/svn/trunk/src/fileformats.c
edit after further research:
Looking at the source code of Allegro v4.4.2, load_bmp() only accepts the variants where the header has size 12 (a so-called OS/2 bitmap header) and a header of size 40 (BITMAPINFOHEADER). It will refuse other formats, most notably the V4 and V5 variants added by Microsoft at the time of WinNT/95 and Windows 98 respectively.
(If you open images with a hex editor, the DIB header size is at offset 14: 0x28 = 40 = OK for allegro 4, 0x6C = 108 = KO for allegro 4)
Allegro 5 should be able to load it. A4 is from like the 1990s, no big surprise newer formats are not supported.
This is a known problem.
Allegro's builtin BMP image loader doesn't support newest format.
gimp 2.8 defaults to new version of BMP format by default (ver 5 if memory serves).
If you want the old format, when you export to BMP,
make sure this option is checked (see attached pic):
Compatibility Options > Do not write color space information
This will create BMP files compatible with Allegro4 and Allegro5 image loader code.
If you decide to upgrade to Allegro5 you'll want to disable the native image loading when building the libaray, in order to read those old-format BMP's.
If you're trying to be cross-platform you may run into issues.
eg: I couldn't load BMP images with the android port.
Cheers,
Pho75.
P.S: I fought with all this earlier, gave up and switched to PNG.
Allegro 5 loads the examples Chris provided, at least when using the Allegro BMP loader (and not some OS-specific routines). But PNG is recommended.
I know that for Allegro 4.4x you have to watch how you save the .BMP file in GIMP. When you go to Export to BMP (or "save as" in older versions of GIMP), the last pop-up dialog before saving will have an "Advanced Options" menu option. Inside there you need to select 24-bit RGB (if memory serves me) for the file to display correctly in Allegro 4. Remember, even if you use transparency in your game, Allegro 4 uses hot pink for that, not an alpha layer.
I haven't used Allegro 5, so I can't say if it has the same problem.
Edit: Reading your second post, I see you've tried different bit depths. But I'll leave this post as-is for anyone who may need to know this information.