Are you sure you're using real skyboxes (on the RenderSettings) or are you creating yourself a large cube? I've never seen any problem with skyboxes (except when the art itself has artifacts). How are you setting up your material (six textures, spheremap, etc.?) Can you post some screenshots?