Album covers are always stretched to a perfect square after adjusting for aspect ratio, so yes, rectangular images will end up looking bad. MrD is probably right that the aspect ratio overall is not set correctly for you. If you have a widescreen monitor you need to calculate your aspect ratio and set MonitorAspectRatio in jukebox.ini to that value. For example, if you have a 16:9 monitor, your aspect ratio is 16 divided by 9 or 1.777. Thus, you would have MonitorAspectRatio=1.777 in jukebox.ini.
--Chris