The sooner you start speaking with a native, the better!
When learning a language, you are necessarily learning a whole new structure of communication and possibly even thought (this is still a heated debate among linguists and psycholinguists). Everything from grammar and syntax to vocabulary to non-verbal cues and beyond is essentially foreign. Though learning from books or other resources is okay, you are still limited to your understanding of what that particular resource is teaching you. If, for some reason or another, you misunderstand or misinterpret the grammar or other component of the language and continue to practice incorrectly, you will cement the wrong grammar, pronunciation, &c. in your mind that will take much longer to correct at a later date.
When working with a native speaker, they will be able to correct you immediately so you do not learn incorrectly. They can help guide you through the nuances and connotations of the language so that you are less likely to mess up in conversation [1][2].
So far, I have only addressed studying with a native speaker, when the native speaker is trying to aid in your language learning. This is a subset of conversing with a native speaker as they are trying to help you in your acquisition.
When conversing with an L1 speaker, much of the responsibility for proper communication and learning relies on the L2 speaker. There are many proposed frameworks for this, but none have been accepted as "the answer". Though not technically a language learning concept, self-confidence is crucial to pursuing language acquisition.
One theme found in many frameworks (see Strategies in Learning and Using a Second Language) is the concept of self-awareness in language use. Other important themes related to this are active corrective listening, the use of circumlocution, speech mimicking, mirroring, and summarization, grouping, deduction, imagery, elaboration, inference, recombination, and translation. (A more complete list can be found in Strategies, p. 76.) I will only discuss a few of these.
Active Corrective Listening
When unsure of how to say a particular phrase, rather than not speak at all, speak as best as you can generate the sentence, and then listen to the L1 speaker. Often, native speakers will repeat back part of the sentence with the corrected grammar as a way to ensure that they understood what was communicated.
For example, in Chinese, if you wanted to asked if someone wanted to go with you to the movies, you would say (this is a gloss) "You want not-want with me go watch movies?" English speakers would place the "with me" part of the sentence at the end if asking this in English. However this is incorrect in Chinese. So, if the L2 speaker asked (incorrectly) "You want not-want go watch movies with me?", the L1 speaker would commonly respond with something like, "Yes, I want with you go watch movies." which uses the proper way to incorporate "with (somebody)" into the sentence.
Observing the corrections that the native speaker inserts into his/her responses and immediately incorporating them into your speech (ie. responding with something like, "Great! I'm happy you want with me go watch movies!") reinforces the proper usage and improves comprehension.
Summarization
When communicating with a native speaker, occasionally summarizing the conversation provides feedback to check understanding. If the summary proves to be incorrect or incomplete, it gives the native speaker an opportunity to jump in and clarify something that may be unclear or wrong.
Circumlocution
This is also known as lexical substitution. When you do not know a word or phrase or are unsure of a word usage, you can "talk around" the word or phrase and allow the native speaker to provide the word you are looking for, or to verify your word usage. Even among native speakers, this is what most people do when the word or phrase is on "the tip of their tongue".
Overall, when to start conversing with a native speaker is not as important as how to start conversing with a native speaker. I have had experience in this regard. I spent 11 weeks learning Chinese, and then got immersed completely when I flew to Taiwan for two years to converse with strangers about anything and everything. (I was a Mormon missionary.) The sooner, the better, but still supplement that with your own personal studying.