Thank you desmond! I will look over it more in the morning. From a quick glance it looks like you preload the gfx, store it to memory, and destroy the original as its cloned.
I think thats my problem is Im not destroying the background bmp before switching them out.
Edit: Wow who would have thought al_destroy_bitmap(background_image); would do just that lol.
So I just tested that real quick in an if statement after reviewing how you loaded your gfx and it worked, thanks I think I got the basic concept!
if(collision)
{
al_destroy_bitmap(background_image);
background_image = al_load_bitmap("data/gfx/new_background_image.tga");
}