Sorry, more commands.

albino@tuxes:~$ ls -l Desktop/
total 16
-rwxr-xr-x 1 albino albino 14897 Jun  5 15:40 openoffice.org3-startcenter.desktop


albino@tuxes:~$ ls -ld Desktop/
drwxr-xr-x 2 albino albino 4096 Jun  5 15:40 Desktop/

If you get the warning that it can't be marked executable by the utility then there must be something wrong with permissions of the Desktop folder.

Create a new launcher on the desktop, but don't doubleclick on it yet. Open a terminal and post here the output of these 2 commands:

ls -ld Desktop
ls -l Desktop

The "Untrusted" warning pops up when you want to launch a .desktop file that is not executable. Do the .desktop files you create have executable permission set? Do you get a warning that the launcher cannot be marked executable?

In any case, you be able to make it work by clicking "mark as trusted" when you run a launcher. Dropping severity to minor.

Dev hint: gnome-panel package, gnome-panel/libpanel-util/panel-keyfile.c, _panel_key_file_make_executable

What's the contents of that .desktop file? Did you create it in the same way as I described?

I can't reproduce this error on my fresh installation. I right-clicked on the desktop, selected "Create Launcher..." and filled the fields as follows.

Type: Application
Name: gedit editor
Command: /usr/bin/gedit
Comment: Editor

After clicking on OK the new icon appeared on the desktop and when I double click it, gedit starts