Thank you so much for your answers. I love you community people !
Now I realize it is a vsync issue. There's actually nothing specific to primitives. I have the same problem with bitmaps.
To answer you question, Peter, I did just use Xubuntu's standard screen capture utility to make the screenshot. And that screenshot fairly well renders what the look can grasp when seeing things move on the screen.
So, the problem seems to be that allegro can't access the vsync from my graphic card's driver. I've tried to add al_set_new_display_option(ALLEGRO_VSYNC, 1, ALLEGRO_REQUIRE) before setting up the display to force the use of vsync. But in that case, the display just isn't created.
I've also tried putting al_wait_for_vsync() before al_flip_display(): the framerate drops to about 10fps and there's still the tearing...
I've tried if it was better with real ALLEGRO_FULLSCREEN (instead of ALLEGRO_FULLSCREEN_WINDOW or normal windowed mode), but it's not.
So I don't really know what to do. I'll try digging into triple buffering, but I'm afraid it will not help, since if allegro doesn't know the vsync of the graphic card, the problem would probably be the same.