Fully non-linear kinetic simulations of electron plasma and ion acoustic waves (IAWs) have been carried out with a new multi-species, parallelized Vlasov code. The numerical implementation of the Vlasov model and the methods used to compute the wave frequency are described in detail. For the first time, the nonlinear frequency of IAWs, combining the contributions from electron and ion kinetic effects and from harmonic generation, has been calculated and compared to Vlasov results. Excellent agreement of theory with simulation results is shown at all amplitudes, harmonic generation being an essential component at large amplitudes. For IAWs, the positive frequency shift from trapped electrons is confirmed and is dominant for the effective electron-to-ion temperature ratio, Z T-e/T-i greater than or similar to 10 with Z as the charge state. Furthermore, numerical results demonstrate unambiguously the dependence [R. L. Dewar, Phys. Fluids 15, 712 (1972)] of the kinetic shifts on details of the distribution of the trapped particles, which depends in turn on the conditions under which the waves were generated. The trapped particle fractions and energy distributions are derived and, upon inclusion of harmonic effects, shown to agree with the simulation results, completing a consistent picture. Fluid models of the wave evolution are considered but prove unable to capture essential details of the kinetic simulations. Detrapping by collisions and sideloss is also discussed. (C) 2013 American Institute of Physics. [http://dx.doi.org/10.1063/1.4794346]