I am currently in Moab, and will be here for a few more days. I'd like to try some star photography whilst i'm here. I tried tonight, but didn't have too much luck really. Mainly due to not knowing exactly what i'm doing... I am using a 5dmk2 and 17-40.
The settings i tried were f4/17mm/30sec/iso800-1600. 30sec seems too long as there's slight movement in the stars, but it gets so noisy and dont really know what to do about that.
Most probably you still are underexposing. As a rule of thumb we have 20-30s at ISO 3200 and f2.8 to 3.5. So f 4 is borderline here.
Do not worry too much. Set ISO 3200-6400 and trust in modern noise reduction software, e.g. ACR of CS6 package does a very good job.
Shoot raw and use "long exposure noise reduction" ON.
Have fun and show us your results
Bump up your ISO. Disable auto focus and set the lens to infinity which is the vertical line where the "L" begins. Infinity in Canon isn't all the way racked. Use mirror lock, use a remote. If you don't have a remote, put it in timer so you don't touch the camera while the exposure is going on.
If you have a forergound, paint with light i.e. using a strong flashlight but do strokes and do not keep the light in one place.
Your ability to minimize star trails or elongated stars depends on the focal length and exposure time. The longer the focal length the shorter the exposure time to minimize star trails. I normally shoot 15mm fisheye, f/2.8, ISO 1600 in totally dark but clear sky as my base and adjust as needed.