TL;DR: It's best to support both ALLEGRO_FULLSCREEN and ALLEGRO_FULLSCREEN_WINDOW to maximize the number of people who can run your game full-screen.
ALLEGRO_FULLSCREEN and ALLEGRO_FULLSCREEN_WINDOW are two completely different approaches to running a full-screen interface and, unfortunately, ALLEGRO_FULLSCREEN works best for some people, and ALLEGRO_FULLSCREEN_WINDOW works best for others.
I've actually made it possible in my project to choose which fullscreen mode to use and have an information bar saying to use the "Full Window" mode if trouble arises with the standard fullscreen mode.
The difference between the two interfaces is that ALLEGRO_FULLSCREEN actually signals the OS to run a full-screen application, and this is what you SHOULD be doing since some background software like virus scanners and firewall programs may behave differently while a full-screen application is running, either by avoiding running updates or other such things.
ALLEGRO_FULLSCREEN_WINDOW creates a borderless, titleless window that fills the entire screen. For some people, this works fine. For other people, there will be issues, such as the task bar showing up overtop. This mode is also still technically a windowed mode, meaning things that background applications that detect full-screen applications won't detect this. ALLEGRO_FULLSCREEN_WINDOW also has the limitation of being unable to be set to a custom resolution, though really, that's not that big a deal nowadays, so long as you're developing your program to run at multiple resolutions.
That said, each time you call al_set_new_display_flags() you're overwriting the previous flags sent. Thus your initial setting of ALLEGRO_FULLSCREEN_WINDOW is being forgotten. You don't actually have to use the ALLEGRO_NOFRAME flag unless you're creating a borderless window that does NOT fill the entire screen.