When you are using a Windows Azure queue, you have to be quite particular how you name it. The rules are:

The queue name must be a valid Domain Name System (DNS) name, conforming to the following naming rules:

1. A queue name must start with a letter or number, and may contain only letters, numbers and the dash (-) character.
2. The first and last letters in the queue name must be alphanumeric. The dash (-) character may not be the first or last letter.
3. All letters in a queue name must be lowercase.
4. A queue name must be from 3 to 63 characters long.

from Naming Queues on MSDN

So rather than having to remember those rules each time, here is a function to validate your queue names.

        /// <summary>
        /// Ensures that the passed name is a valid queue name.
        /// If not, an ArgumentException is thrown
        /// </summary>
        /// <exception cref="System.ArgumentException">If the name is invalid</exception>
        /// <param name="name">The name to be tested</param>
        public static void ValidateQueueName(String name)
        {
            if (String.IsNullOrEmpty(name))
            {
                throw new ArgumentException(
                    "A queue name can't be null or empty", "name");
            }

            // A queue name must be from 3 to 63 characters long.
            if (name.Length < 3 || name.Length > 63)
            {
                throw new ArgumentException(
                    "A queue name must be from 3 to 63 characters long - \"" 
                    + name + "\"", "name");
            }

            // The dash (-) character may not be the first or last letter.
            // we will check that the 1st and last chars are valid later on.
            if (name[0] == '-' || name[name.Length - 1] == '-')
            {
                throw new ArgumentException(
                    "The dash (-) character may not be the first or last letter - \"" 
                    + name + "\"", "name");
            }

            // A queue name must start with a letter or number, and may 
            // contain only letters, numbers and the dash (-) character
            // All letters in a queue name must be lowercase.
            foreach (Char ch in name)
            {
                if (Char.IsUpper(ch))
                {
                    throw new ArgumentException(
                        "Queue names must be all lower case - \"" 
                        + name + "\"", "name");
                }
                if (Char.IsLetterOrDigit(ch) == false && ch != '-')
                {
                    throw new ArgumentException(
                        "A queue name can contain only letters, numbers, "
                        + "and and dash(-) characters - \"" 
                        + name + "\"", "name");
                }
            }
        }

Neil