I got the game working with the Universal Widescreen Patcher and UI fix. The problem is that the resolution of my monitor is 1366x768, with that resolution it's recommended to patch the game to run on a higher resolution (in my case 1530x864) and then let the GPU downscale it to the monitor's native resolution. The problem is that my GPU simply won't do it. I have an AMD 5770 graphics card, I've tried different drivers and the ATI GPU Scaling Fix for Windows 7, and sadly, it didn't help. Is there another way to downscale the resolution somehow?

PS. I also tried running the game with Flawless Widescreen, but that didn't work at all.

Try looking here - http://forums.guru3d.com/showthread.php?t=366244
or here - http://levelupguides.com/final-fantasy-xiii/change-resolution-without-gedosato/
You can also try using GeDoSaTo, but I don't see this game on compatibility list.

I gave Flawless Widescreen another shot and now the game works perfectly, so no downscaling is needed anymore. Still, thanks for those links.