As a crossword entry, A Bug's Life most certainly should include the A. Many song titles begin with the word A and, if they were used in a crossword, most of them should keep the A. The title of Frankie Avalon's A Boy Without A Girl might make sense without the A but you'd definitely have to include the A if you used Perry Como's A You're Adorable.
I've seen phrases beginning with THE in quite a few puzzles but I've never seen a crossword with "A" phrases. I think such a puzzle could be fun, provided you can come up with several phrases in which the A can not be dropped without changing the meaning.