"@" in perl means array/list

perl -p -e 's/^@(.*)/\@New_Title_$1/' input_file.fastq > new_fastq_header_file.fastq

@shenwei356's is right when he says that you need to escape the @ character with the inverted slash \ if you want to use it inside a regex pattern. additionally, you don't need to store all header in $1, but simple to replace the initial @ character:

perl -pe 's/^@/\@New_Title_/' input_file.fastq > new_fastq_header_file.fastq

but it looks like you are trying to edit only sequence headers just by looking at the first character, and you can't do that since the @ character can also appear in the quality string. a quick way to workaround this could be replacing odd lines only:

perl -pe '$i = $i ? 0 : 1; s/^@/\@New_Title_/ if $i' input_file.fastq > new_fastq_header_file.fastq

although the proper way to do it would be replacing 1st line only of each 4 lines group:

perl -pe '$i++; s/^@/\@New_Title_/ if $i % 4 == 1' input_file.fastq > new_fastq_header_file.fastq