1. Prevent our users from creating CTASKs until that Change Record has been submitted for approval.
You can right-click that related list and personalize the list control. Here's a wiki article describing the process...
http://wiki.service-now.com/index.php?title=Personalizing_Lists#Advanced_Control

2. Prevent our Business Rule that sends the CTASKs to our 3rd party from running for Changes that have not been submitted for approval.
You just need to add a condition to the business rule to look at the attached change request approval field. If the approval field is 'not requested' then the rule will not run. Something like this should work...
current.change_request.approval != 'not requested'