Yeah, AA is a big performance hog. You should be able to run at 4x internal rez though, maybe you could post the rest of your settings (including the settings you get if you right-click the game in the game list and pick preferences or whatever) and we can give you some tips.. And yes, those are the patches that are out there for Xenoblade. I'm personally not using the high-res patch though because I prefer the original look.
The characters don't look high rez but I can at least tell that the character pics for their hp, etc are up-scaled.
The gameconfig (right clicking game in Dolphin list) has: enable duo core, enable MMU, enable BAT, MMU Speed Hack, Accurate VBeam emulation, Speed up disc transfer rate, Enable Block Merging, DSP HLE emulation (fast), enable widescreen, disable wiimote speaker, and ZTP Hack all checked.
Dolphin config just has: Enable Duo Core (speedup), Enable Idle Skipping (speedup), JIT Recompiler (recommended) checked. Should I check lock thread to cores?
Audio is on DSP HLE Emulation (fast) with enable DTK music and enable Audio Throttle checked.
I have the wii set to 16:9 aspect ratio, should I set that back to auto?
Graphics on Direct3D9 and I have force aspect ratio at 16:9
Enhancements at 3x Native, AA 4x, Anisotropic Filtering 16x (maybe I should lower this?) with scaled EFB copy and per pixel lighting checked.
On another note, while I was typing this out, the game dimmed and put up some error about the wiimote getting disconnected or something along those lines. I couldn't snap the game out of it with my 360 controller and now I've lost all my progress from tonight

Has anyone encountered this? Does this just come from inactivity? That's going to suck. I guess I'll just have to save the game if I'm going to stop playing for more than a minute.