@mcc .desktop files are usually placed in menus and autostart directories separate from the thing they're running: You don't normally see them in the directory with an application, because they don't work very well with relative paths. I think that's deliberate for security. :-\ You're usually better just using a shell script. But you can be hacky and do:
Exec=sh -c "exec $(dirname %k)/script.sh"
To run script.sh relatively from a .desktop file... Looks a bit ropey though.