Can these unit tests be improved?
Assuming that I've correctly managed to extrapolate the SUT and friends from the question, I'd reduce the tests to the following. Please note that this focuses only on AutoFixture mechanics, and not on the general design of neither test nor SUT API.

AFAICT, the following tests state the same as the tests in the OP, but reduced to only the necessary statements. Still, I agree with Nikos Baxevanis that it would be possible to reduce these tests dramatically with xUnit.net instead of MSTest.

using System.Collections.Generic;
using System.Linq;
using FakeItEasy;
using FirstAutoFixtureReviewForKellySommers;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using Ploeh.AutoFixture;
using Ploeh.AutoFixture.AutoFakeItEasy;
using Ploeh.AutoFixture.Kernel;

namespace HaywireMQ.Server.Tests
{
    /// &lt;summary&gt;
    /// Tests for HaywireServer
    /// &lt;/summary&gt;
    [TestClass]
    public class HaywireServerTests
    {
        [TestMethod]
        public void Should_use_defaults_without_ModuleCatalog()
        {
            // Given
            var fixture = new Fixture().Customize(new TestConventions());

            // When
            var target = fixture.CreateAnonymous&lt;HaywireServer&gt;();

            // Then
            Assert.IsInstanceOfType(target.MessageStore, typeof(InMemoryMessageStore));
            Assert.IsInstanceOfType(target.MessageChannel, typeof(InMemoryMessageChannel));
        }

        [TestMethod]
        public void Should_use_ModuleCatalog()
        {
            // Given
            var fixture = new Fixture().Customize(new TestConventions());

            var catalog = fixture.Freeze&lt;ModuleCatalog&gt;();
            fixture.AddManyTo(catalog.MessageStores, 1);
            fixture.AddManyTo(catalog.MessageChannels, 1);

            // When
            var target = fixture.CreateAnonymous&lt;HaywireServer&gt;();

            // Then
            Assert.AreEqual(catalog.MessageStores.Single(), target.MessageStore);
            Assert.AreEqual(catalog.MessageChannels.Single(), target.MessageChannel);
        }

        [TestMethod]
        public void Should_create_MessageQueue()
        {
            // Given
            var fixture = new Fixture().Customize(new TestConventions());

            var catalog = fixture.Freeze&lt;ModuleCatalog&gt;();
            fixture.AddManyTo(catalog.MessageStores, 1);

            List&lt;string&gt; ids = fixture.CreateMany&lt;string&gt;(1).ToList();
            A.CallTo(() =&gt; catalog.MessageStores.Single().GetQueues()).Returns(ids);

            var target = fixture.CreateAnonymous&lt;HaywireServer&gt;();

            // When
            target.Start();

            // Then
            A.CallTo(() =&gt; catalog.MessageStores.Single().GetQueues()).MustHaveHappened();
            Assert.AreEqual(1, target.MessageQueues.Count);
            Assert.AreEqual(ids.First(), target.MessageQueues[0].Id);
        }

        private class TestConventions : CompositeCustomization
        {
            public TestConventions()
                : base(
                    new AutoFakeItEasyCustomization(),
                    new GreedyHaywireServerCustomization())
            {
            }
        }

        private class GreedyHaywireServerCustomization : ICustomization
        {
            public void Customize(IFixture fixture)
            {
                fixture.Customize&lt;HaywireServer&gt;(c =&gt;
                    c.FromFactory(new MethodInvoker(new GreedyConstructorQuery())));
            }
        }
    }
}