For enciphering messages with AES in CTR mode, do I need a different key for each message? I have written a program to run AES in CTR mode with keys of 128,192 or 256 bits and checked it gives correct results with the data given in section F.5 at http://csrc.nist.gov/publications/nistpubs/800-38a/sp800-38a.pdf

The program chooses a different nonce for each message that is enciphered. Do I need a different key for every message as well? or will a single key with a differing nonce provide all the security that is needed?
To fully answer your question, let me go over the exact way in which CTR mode works.  Following the diagram below:



CTR mode takes in a 96 bit nonce and a 32 bit counter that is incremented with each block.  This 128 bit value is then put through, let's say AES encryption, with either a 128, 192 or 256 bit key.  This same key is used with every block.  A 128 bit output from the AES encryption is produced and this value is then XORed with the first 128 bit block of plaintext.

Now, we have produced the first block of ciphertext.  This same technique is done for each block of plaintext using the same key, but simply incrementing the counter each time.  Due to this design, padding is not necessary for the final block of plaintext and each block can be encrypted at the same time in a parallel fashion.  You should never repeat nonce/key pairs, as this will make it very easy for an adversary to gain knowledge of information.  CTR mode is basically a key stream that produces an overall key to be XORed almost like a One Time Pad.

You may repeat keys for different messages, as long as the nonce and counter are different.