AWS SDK for PHPを例に出しますが、おそらく他でもそうかと思います。

例として、

example.com に ass IN CNAME example.org を追加もしくは既存レコードの変更を行いたい

とします。

#症状1

ここを参考に、

PHP

try{
        $result = $route53Client->changeResourceRecordSets(array(
                'HostedZoneId' => '(example.comを指すHostedZoneId)',
                'ChangeBatch' => array(
                        'Changes' => array(
                                array(
                                        'Action' => 'UPSERT',
                                        'ResourceRecordSet' => array(
                                                'Name' => 'ass',
                                                'Type' => 'CNAME',
                                                'ResourceRecords' => array(
                                                        array(
                                                                'Value' => example.org
                                                        )
                                                )
                                        )
                                )
                        )
                )
        ));
}catch(Exception $ex) {
        echo "execution failed:".$ex->getMessage()."\n";
        return;
}

みたいな感じで投げると
execution failed:Invalid request と言われる。

#原因1

面倒臭がらず、__TTL__をちゃんと設定しましょう。

#症状2

PHP

try{
        $result = $route53Client->changeResourceRecordSets(array(
                'HostedZoneId' => '(example.comを指すHostedZoneId)',
                'ChangeBatch' => array(
                        'Changes' => array(
                                array(
                                        'Action' => 'UPSERT',
                                        'ResourceRecordSet' => array(
                                                'Name' => 'ass',
                                                'Type' => 'CNAME',
                                                'TTL' => 300,
                                                'ResourceRecords' => array(
                                                        array(
                                                                'Value' => example.org
                                                        )
                                                )
                                        )
                                )
                        )
                )
        ));
}catch(Exception $ex) {
        echo "execution failed:".$ex->getMessage()."\n";
        return;
}

のように投げると
execution failed:RRSet with DNS name ass. is not permitted in zone example.com.
と言われる

#原因2

'Name' => 'ass', ではだめです。面倒臭がらずに 'Name' => 'ass.example.com',としましょう。

#まとめ

Web Consoleをいっぱい使ってる人だと、AWS側が自動で色々やってくれるので、
こういう細かいところで引っかかりがちな気がします。