I've been thinking about that as well. Here's how we're doing it right now.

When an Allegro program starts on OS X, the magic main runs _al_osx_run_main, which is in src/macosx/osx_app_delegate.m. It first tries to load a "nib" for the main menu (I suspect that's an Interface Builder thingy, never looked at this myself). Failing that, it creates the standard menu entries programmatically. The name of the menu item is taken from the name of the bundle, or, failing that, from the name of the running process:

NSString* title = nil;
NSDictionary* app_dictionary = [[NSBundle mainBundle] infoDictionary];
if (app_dictionary) 
{
    title = [app_dictionary objectForKey: @"CFBundleName"];
}
if (title == nil) 
{
    title = [[NSProcessInfo processInfo] processName];
}

What I might expect is that Allegro's al_set_app_name() function would set the name here. The problem is, that runs from the user main() function, after the above code is called. I suppose it's possible to change the title later, but this would be a bit of a hassle.

That said, there are two ways for you to override the default name that Allegro assigns, which may be a better alternative in practice. The first is to create the menu yourself using the mentioned "nib", the second is to set the application name in the bundle's info.plist (see http://developer.apple.com/library/mac/#documentation/Cocoa/Conceptual/ObjCTutorial/08Configuring/08Configuring.html). That's probably what you will want to do.
Note I haven't actually tried either.