Semi-complex passwords would be much less secure than complex passwords (but more secure than simple passwords). Ideally, a password should be long, have numbers, special characters, capital letters, and lowercase letters. Long passwords are especially to be desired because each additional letter makes the password 26 times harder to guess if only lower case characters are used. If uppercase characters are also required, this makes it 52 times harder to guess per additional character. If numbers are added, each character makes it 62 times harder to guess. Special characters increases this further.
Keep in mind that a 5 character password can be easily brute forced with modern technology and is not very secure, so you will want much longer passwords. As technology advances, even longer passwords (or other methods of security) will be required. As for the effects on mobile phones and operating systems, it depends on their implementation if adding these requirements would cause a problem, but it shouldn't. I have encountered websites that don't like special characters in passwords, for example, but this could be fixed by the site's implementation.
Another thing to consider is that long passwords on a phone are harder to enter, as pointed out by Bill Weiss in the comments. For this reason, it might be good to consider alternate authentication technologies (e.g. pin / biometric / tokens) as well. This has prompted me to ask the following question here, which may come up with better ways to authenticate than passwords: What is a good way to authenticate a user to a smart phone?
The following analysis from xkcd.com shows the value of longer vs. more complex passwords (although the example they post might be more easily cracked with a dictionary attack).