The problem with using an Ubuntu derivative is that we don't know what
kernel, version of GNOME and Ubuntu it is based on. That means we are
shooting arrows in the dark. Have you considered using Ubuntu? Then you can
say, I am using Karmic or whatever and that makes it a lot easier to
troubleshoot. You can change the theme and add to the repos to suit your
personal preference, but having a solid base to build on is important. This
goes for users of Ultimate and other derivatives as well.

General advice: For wireless issues consider installing madwifi for drivers
and wicd (pronounced wicked) for connection problems.

If you can connect to a wireless network, your wireless hardware is working.
Sometimes you can "see" a network, but the signal is not consistently strong, or
there is interference from another network on the same channel.