I figured it out. Promit, thanks for the hint.

I set up the app to start in a standard resolution (1024x768 or 800x600) windowed. As long as I didn't resize the window, when I toggled back and forth to fullscreen, it went to fullscreen at one of those standard resolutions. But after resizing the window, it's BackBuffer Width and Height are at some odd resolution (like 814x403) that the adapter doesn't support, so when I try to go to fullscreen at that resolution it throws the exception. The solution was to override the windowed resolution and set it to one of the supported resolutions (something close to the windowed resolution) before going full screen.

Interestingly enough, as a shortcut to enumerating proper PresentParameters I tried using a bit of the SlimDX SampleFramework, just as a quick test. Assuming that "FindValidSettings" would tell me if I was doing anything wrong I did the following to convert from PresentParameters to SampleFramework.DeviceSettings:

SampleFramework.DeviceSettings ds = new SampleFramework.DeviceSettings();
ds.AdapterOrdinal = createParams.AdapterOrdinal;
ds.BackBufferCount = presentParams.BackBufferCount;
ds.BackBufferFormat = presentParams.BackBufferFormat;
ds.BackBufferHeight = presentParams.BackBufferHeight;
ds.BackBufferWidth = presentParams.BackBufferWidth;
ds.DepthStencilFormat = presentParams.AutoDepthStencilFormat;
ds.DeviceType = createParams.DeviceType;
ds.EnableVSync = presentParams.PresentationInterval != PresentInterval.Immediate;
ds.MultisampleQuality = presentParams.MultisampleQuality;
ds.MultisampleType = presentParams.Multisample;
ds.RefreshRate = presentParams.FullScreenRefreshRateInHertz;
ds.Windowed = false;
ds = SampleFramework.DeviceSettings.FindValidSettings(ds);

However, even at an odd BackBuffer WidthxHeight of 814x403, "FindValidSettings" didn't make any changes and it still threw the exception.

Maybe one of the SlimDX people can tell me what I was doing wrong.

Thanks to all of you for your input.