Is the game in the default directory? If not, then, I think, that is your problem. The game didn't run for me when I choose a custom directory... Make sure the game is in the default directory, "C:/Phantasy Star Online" or something like that. If you're game is not in the default directory, then uninstall and reinstall with the default options.
Get back to us, if your problem persists.
BTW: I'm using Windows 7 64bit.