I assumed that was a typo, and an email to the article's author confirmed it, that he meant to say you were allowed to add two extra nucleotides, not amino acids. The section before the puzzle discussed adding on one or two nucleotides, so I figured that's what he meant to say in the puzzle text. Just a note: the above program only generates one solution. If you're allowed to glue six extra bases, it would generate alot more :-)

Update: BTW, updated code to a new name - DNA::Stitch. I figured short was good...(or maybe DNA::Glue or DNA::Protein::Glue...?)

Update: Hmm, with a target sequence of length 250 or more, this recursive solution might not cut it...(then again...)