some HD screen recording software
What software? What export settings, specifically codec, frame size & frame rate.
The more specific you can be about your setup the more likely we will be able to help you.
Final Cut Express is designed to work natively with QuickTime DV (NTSC/29.97 or PAL/25) and QuickTime AIC (Apple Intermediate Codec 1080i50/60 or 720p25/30). Your video clips need to conform to one of these selections. FCE does not support 1080p or 24fps footage although there are some workarounds for 1080p. If you search the FCE discussions you will find previous posts about dealing with 1080p footage.
When you import DV, HDV or AVCHD video directly from a camcorder, FCE takes care of saving the video in the proper format/codec provided you have first selected the appropriate FCE Easy Setup (see FCE > Easy Setup.) This is not the case when you import video from other sources - usually you have to convert or transcode those clips yourself first. The default FCE Easy Setup is DV NTSC - that's why you got 4:3 standard def output. If you have other types of video, you need to change your Easy Setup before creating a sequence, importing clips and editing.
Because FCE is based on QuickTime it is possible to import all sorts of video but that doesn't mean that FCE can actually work with it, work with it well, or produce acceptable results. The best approach is to make sure your clips match what FCE is capable of editing natively.