I'm gonna have to agree with Obesebear, the original looks better.
In particular, take note of the lower space between the pieces of pavement, or the texture on the back wall. In the original, pixellated version, it retains some depth, but the lower contrast and blurring of the modified version causes these things to look painted on. In general, this form of upscaling tends not to play nicely with thin, dark lines on light surfaces.
One thing to keep in mind is that FSAA is meant to be used for antialiasing 3D assets, not upscaling 2D assets. When you play a proper 3D game (not something with prerendered backgrounds) with FSAA, what it does is render the scene at a higher resolution, and then DOWNSCALE it back to the display resolution. Since the original data is vector-based, it can render at a theoretically unlimited resolution with no quality loss, limited only by your graphics card's abilities. What this means is that the extra data for higher resolutions is there, and used to average what each pixel should be.
FF8's backgrounds are 2D raster images. The original 3D polygon data is not there anymore. FSAA does not have a larger image to pull data from. What you are probably doing, in "upscaling with FSAA" is in fact probably just a standard bilinear or trilinear upscale; basically taking a nearest-neighbor upscale and applying a blur filter to it.
tl;dr - FSAA is useful for antialiasing vector images as they're rendered, not for enlarging raster images after they've been rendered. You'd be far better off checking out OnOne Software's
Perfect Resize 7. You want a scaling method that uses a bunch of sophisticated math stuffs to guess what SHOULD be in the extra pixels you're creating, not one that relies on the data already being available.